Leetcode: Word break
Given a string s and a list of words, return True if the string can be constructed from any combination of the words and False otherwise. The alphabet contains only lowercase English characters.
My initial idea was to replace all occurrences of a word in the string s. The problem with this approach is that a string aabb with the words ['ab'] is considered valid, while it is not. I then tried on adding breaking characters (.) to prevent this. It worked although very slowly.
My next approach was to start only from the beginning and remove the current word from s if it was the prefix. The advantage is that this alrogrithm is relatively straightforward. The disadvantage is that it is relatively time-intensive. The same words will be checked over and over again.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
if s == "":
return True
res = False
for i, word in enumerate(wordDict):
if s.startswith(word):
res = res or self.wordBreak(s[len(word):], wordDict)
return resmap or dictionary, that contains all previously seen and invalid or valid substrings. Before going into the recursion, we check whether the word was already seen and if it was, we return the previously computed value.
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
memo = {}
def inner(s, wordDict):
if s == "":
return True
if s in memo:
return memo[s]
for word in wordDict:
if s.startswith(word):
if inner(s[len(word):], wordDict):
memo[s] = True
return True
memo[s] = False
return False
return inner(s, wordDict)
if __name__ == '__main__':
s = Solution().wordBreak
print(s('leetcode', ["leet","code"]), True)
print(s('applepenapple', ["apple","pen"]), True)
print(s('catsandog', ["cats","dog","sand","and","cat"]), False)
print(s('ccbb', ['cb']), False)
print(s('cbca', ['bc','ca']), False)
print(s("ddadddbdddadd", ["dd","ad","da","b"]), True)
Runtime: 75 ms, faster than 25.22% of Python3 online submissions for Word Break. Memory Usage: 14.2 MB, less than 14.55% of Python3 online submissions for Word Break.A good explanation on dynamic programming and memoization can be found here.