Teaching Kids Programming – Break a String into Words (Word Break) via Recursion with Memoziation – Top Down Dynamic Programming Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:
Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.

Example 2:
Input: s = “applepenapple”, wordDict = [“apple”,”pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.

Example 3:
Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: false

Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

Break a String into Words (Word Break) via Recursion with Memoziation – Top Down Dynamic Programming Algorithm

We can bruteforce which could be Depth First Search or Breadth First Search. The idea is to bruteforce next split point and recursive jump to it if the substring is in the given list. The time complexity is because for a given string size of N, there are N+1 ways to split it, and in the worst case, for each split point, we have two choices.

A simple and quick optimisation is to add a @cache keyword to remember the intermediate results aka dfs(i) values. There are at most N states for dfs function, and the time complexity is improved to . The string slicing takes O(N) time, and for each recursive call, we need a for loop. This is also known as Top Down Dynamic Programming aka Recursion with Memoziation.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        @cache
        def dfs(i):
            if i == len(s):
                return True
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in w and dfs(j):
                    return True
            return False
        return dfs(0)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        @cache
        def dfs(i):
            if i == len(s):
                return True
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in w and dfs(j):
                    return True
            return False
        return dfs(0)

Another slightly different implementation would be to iterate over the allowed words, and check if we can match the next substring. Same time complexity O(N^3).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        @cache
        def dfs(i):
            if i == len(s):
                return True
            for j in w:
                if s[i:i+len(j)] == j and dfs(i+len(j)):
                    return True
            return False        
        return dfs(0)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        @cache
        def dfs(i):
            if i == len(s):
                return True
            for j in w:
                if s[i:i+len(j)] == j and dfs(i+len(j)):
                    return True
            return False        
        return dfs(0)

For above Recursive Depth First Search with Memoziation or without it aka Bruteforce algorithm, the Recursion depth can go up to N therefore the space complexity is O(N).

Word Break Algorithms

• Teaching Kids Programming – Dynamic Programming Algorithm to Break a String using Given Words (Word Break)
• Teaching Kids Programming – Break a String into Words (Word Break) via Breadth First Search Algorithm
• C/C++ Coding Exercise – Word Break (DP, BFS, DFS)
• Teaching Kids Programming – Break a String into Words (Word Break) via Recursion with Memoziation – Top Down Dynamic Programming Algorithm

–EOF (The Ultimate Computing & Technology Blog) —