Word Break Problem


Description

LeetCode Problem 139.

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:

1
2
3
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

1
2
3
4
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:

1
2
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.


Sample C++ Code

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
44
45
46
47
48
49
50
class Solution {
public:
    struct TrieNode {
        TrieNode* arr[26];
        bool is_end;
        TrieNode() {
            for (int i = 0; i < 26; i ++) {
                arr[i] = nullptr;
            }
            is_end = false;
        }
    };
    
    void insert(TrieNode* root, string s) {
        TrieNode* curr = root;
        for (int i = 0; i < s.size(); i ++) {
            int idx = s[i] - 'a';
            if (curr->arr[idx] == nullptr)
                curr->arr[idx] = new TrieNode();
            curr = curr->arr[idx];
        }
        curr->is_end = true;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < wordDict.size(); i ++) {
            insert(root, wordDict[i]);
        }
        
        int l = s.size();
        vector<int> dp(l+1, 0);
        dp[0] = 1;
        
        for (int i = 0; i < l; i ++) {
            if (dp[i] == 0)
                continue;
            TrieNode* curr = root;
            for (int j = i; j < l; j ++) {
                if (curr->arr[s[j]-'a'] == NULL)
                    break;
                curr = curr->arr[s[j]-'a'];
                if (curr->is_end == true)
                    dp[j+1] = 1;
            }
        }
        
        return dp[l];
    }
};




Related Posts

Word Break Problem

LeetCode 139. Given a string s and a dictionary of...

Word Break II Problem

LeetCode 140. Given a string s and a dictionary of...

Stream of Characters Problem

LeetCode 1032. Implement the StreamChecker class as follows. Constructor, initialize...

Maximum XOR of Two Numbers in an Array Problem

LeetCode 421. Given an integer array nums, return the maximum...

Implement Trie (Prefix Tree) Problem

LeetCode 208. Implement a Trie with insert, search, and startsWith...

Camelcase Matching Problem

LeetCode 1023. A query word matches a given pattern if...