Merge pull request prakhar1989#33 from vedangmehta/master

prakhar1989 · prakhar1989 · commit ec4e0689909c · 2016-01-24T13:34:35.000-05:00
Added LCS and updated README and added tests to /tests
diff --git a/README.md b/README.md
@@ -35,6 +35,8 @@ Completed
 - Binary Search Tree
 - Kandane's Algorithm
 - Knapsack Problem (0/1 and unbounded)
+- Longest Increasing Subsequence
+- Longest Common Subsequence
 - Prefix Tries
 - Stack ADT (with example problems)
   - String Reverse
diff --git a/dp/lcs.py b/dp/lcs.py
@@ -0,0 +1,32 @@
+"""
+Problem : https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
+"""
+
+def longest_common_subsequence(s1, s2):
+    # lengths of strings s1 and s2
+    m, n = len(s1), len(s2)
+    # to cache the results
+    cache = [[0 for j in range(n + 1)] for i in range(m + 1)]
+    for i, character_s1 in enumerate(s1):
+        for j, character_s2 in enumerate(s2):
+            if character_s1 == character_s2:
+                cache[i + 1][j + 1] = cache[i][j] + 1
+            else:
+                cache[i + 1][j + 1] = max(cache[i][j + 1], cache[i + 1][j])
+    # LCS is empty by default
+    sequence = ""
+    i, j = m, n
+    # finding the sequence from cache
+    while i >= 1 and j >= 1:
+        if s1[i - 1] == s2[j - 1]:
+            sequence += s1[i - 1]
+            i, j = i - 1, j - 1
+        elif cache[i - 1][j] > cache[i][j - 1]:
+            i -= 1
+        else:
+            j -= 1
+    # returns the length of LCS along with the sequence itself
+    return (len(sequence), sequence[::-1])
+
+if __name__ == "__main__":
+    print(longest_common_subsequence("ABCXYZ","ACBCXZ"))
diff --git a/tests/lcs_test.py b/tests/lcs_test.py
@@ -0,0 +1,11 @@
+import unittest
+import lcs
+
+class TestLCS(unittest.TestCase):
+    def test_lcs(self):
+        self.assertEqual(lcs.longest_common_subsequence("ABCD", "BBDABXYDCCAD"), (4, "ABCD"))
+        self.assertEqual(lcs.longest_common_subsequence("BANANA", "ATANA"), (4, "AANA"))
+        self.assertEqual(lcs.longest_common_subsequence("ABCDEFG", "BDGK"), (3, "BDG"))
+
+if __name__ == "__main__":
+    unittest.main()
