Word Break II Problem


Description

LeetCode Problem 140.

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

1
2
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

1
2
3
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

1
2
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Constraints:

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • 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
51
52
53
54
55
56
57
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 ++) {
            if (curr->arr[s[i]-'a'] == nullptr)
                curr->arr[s[i]-'a'] = new TrieNode();
            curr = curr->arr[s[i]-'a'];
        }
        curr->is_end = true;
        return;
    }
    
    vector<string> ans;
    
    void dfs(string& currS, string& s, int idx, TrieNode* root) {
        if (idx == s.size()) {
            ans.push_back(currS.substr(0, currS.size()-1));
        }    
        if (idx >= s.size())
            return;
        
        TrieNode* curr = root;
        string tempS;
        for (int i = idx; i < s.size(); i ++) {
            tempS += s[i];
            if (curr->arr[s[i]-'a'] == nullptr)
                return;
            curr = curr->arr[s[i]-'a'];
            if (curr->is_end == true) {
                currS = currS + tempS + ' ';
                dfs(currS, s, i+1, root);
                currS = currS.substr(0, currS.size()-tempS.size()-1);
            }
        }
    }
    
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < wordDict.size(); i ++) {
            insert(root, wordDict[i]);
        }
        
        string currS;
        dfs(currS, s, 0, root);
        return ans;
    }
};




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