Teaching Kids Programming – Break a String into Words (Word Break) via Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = “helloworld”, dict = [“world”, “hello”]. Return true because “helloworld” can be segmented as “hello world”.

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 Breadth First Search Algorithm

Using BFS (Breadth First Search) Algorithm, we traverse the search tree in the level-by-level orders. We still need to use a hash set to remember the nodes that we have expanded so we don’t repeatedly search the nodes.

We store the current index, so that when we reach the end, it means that we can break the string using the given words. If the current index is i, we need to expand the jump position from next index to the end, if and only if we can construct a substring from the current position that is allowed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        q = deque([0])        
        seen = set()
        while q:
            cur = q.popleft()
            if cur in seen:
                continue 
            seen.add(cur)
            for x in range(cur + 1, len(s) + 1):
                if s[cur:x] in w:
                    if x == len(s):
                        return True
                    q.append(x)
        return False        

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        q = deque([0])        
        seen = set()
        while q:
            cur = q.popleft()
            if cur in seen:
                continue 
            seen.add(cur)
            for x in range(cur + 1, len(s) + 1):
                if s[cur:x] in w:
                    if x == len(s):
                        return True
                    q.append(x)
        return False        

We can also iterate over the given words, and try to compare if we can construct the next substring from it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        q = deque([0])        
        seen = set()
        while q:
            cur = q.popleft()
            if cur in seen:
                continue 
            seen.add(cur)
            for x in w:
                nx = len(x)
                if s[cur:cur+nx] == x:
                    if cur + nx == len(s):
                        return True
                    q.append(cur + nx)
        return False        

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        w = set(wordDict)
        q = deque([0])        
        seen = set()
        while q:
            cur = q.popleft()
            if cur in seen:
                continue 
            seen.add(cur)
            for x in w:
                nx = len(x)
                if s[cur:cur+nx] == x:
                    if cur + nx == len(s):
                        return True
                    q.append(cur + nx)
        return False        

Time complexity is O(N^3), and 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) —