Adding word break impl

rlishtaba · rlishtaba · Dec 11, 2017 · Dec 11, 2017 · Dec 12, 2017 · Dec 11, 2017
commit d4605d5ce527f79248246381c7c25c80984175c9
diff --git a/py_algorithms/strings/word_break.py b/py_algorithms/strings/word_break.py
@@ -0,0 +1,49 @@
+from typing import List
+
+
+class WordBreak:
+    @staticmethod
+    def apply(word: str, voc: List[str]) -> bool:
+        queue = [0]
+        visited = []
+
+        while len(queue) > 0:
+            start = queue.pop(0)
+            if start not in visited:
+                end = start + 1
+                while end <= len(word):
+                    if word[start:end] in voc:
+                        queue.append(end)
+                        if end == len(word):
+                            return True
+                    end += 1
+
+                visited.append(start)
+        return False
+
+    @staticmethod
+    def dp_apply(word: str, voc: List[str]) -> bool:
+        dp = [False for _ in range(len(word))]
+        length = len(word)
+
+        for i in range(length):
+            for w in voc:
+                w_len = len(w)
+                if w == word[i - w_len + 1:i + 1]:
+                    if dp[i - w_len] or i - w_len == -1:
+                        dp[i] = True
+        return dp[-1]
+
+    @staticmethod
+    def dp2_apply(word: str, voc: List[str]) -> bool:
+        dp = [False for _ in range(len(word) + 1)]
+        dp[0] = True
+
+        for i in range(1, len(word) + 1):
+            j = 0
+            while j < i:
+                if dp[j] and word[j:i] in voc:
+                    dp[i] = True
+                j += 1
+
+        return dp[-1]
diff --git a/tests/py_algorithms/strings/word_break_test.py b/tests/py_algorithms/strings/word_break_test.py
@@ -0,0 +1,10 @@
+from py_algorithms.strings.word_break import WordBreak
+
+
+class TestWordBreak:
+    def test_apply(self):
+        impls = [WordBreak.apply, WordBreak.dp_apply, WordBreak.dp2_apply]
+        voc = ["cat", "cats", "and", "sand", "dog"]
+        for impl in impls:
+            is_possible = impl('catsanddog', voc)
+            assert is_possible is True