<139> Word Break

Posted on Edited on In Views:

Description

Question: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note: The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Leetcode link: 139. Word Break

Quick Sum-up:

  • Input: a string and an array of words
  • Output: a boolean value indicating whether the string can be assembled by the words
  • The string is non-empty.
  • The array is non-empty.

Idea

  1. Compare the string with words in the dictionary. If a word appears in the string, slice the string and put the substring to the next round of matching until the string is empty. => TLE, fail on the 4th case
  2. Use BFS, the queue of BFS stores the start index of next round. In addition, we need to record whether an index has been stored in the queue. => Pass, 68ms

Test cases

Input Output
s="leetcode"
wordDict=["leet", "code"]		 true
s="applepenapple"
wordDict=["apple", "pen"]		 true
s="catsandog"
wordDict=["cats", "dog", "sand", "and", "cat"]		 false
s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaab"
wordDict=["a","aa","aaa","aaaa","aaaaa",
"aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa",
"aaaaaaaaaa"]		 false

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    let startIndex = 0
    
    let isSame = function(startIndex, word) {
        if (startIndex + word.length > s.length)
            return false
        
        for (let i = 0; i < word.length; i++) {
            if (word[i] != s[startIndex + i])
                return false
        }
        
        return true
    }
    
    let q = [0]
    while(q.length) {
        let newQ = {}

        while (q.length) {
            let startIndex = parseInt(q.shift())
            
            if (startIndex == s.length)
                return true
            
            for (let i = 0; i < wordDict.length; i++) {
                if (newQ[startIndex + wordDict[i].length] == undefined &&
                    isSame(startIndex, wordDict[i]))
                {
                    newQ[startIndex + wordDict[i].length] = true
                }
            }
        }
        q = Object.keys(newQ)
    }
    
    return false
};