Friedrich Ewald My Personal Website

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 res
Adding memoization speeds up the solution by quite a bit. Here, we initialize a map 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.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts