Leetcode 0140. word splitting II

【LetMeFly】140. Word splitting II

Force button topic link ：https://leetcode.cn/problems/word-break-ii/

Given a string s And a string dictionary  wordDict , In string  s  Add spaces to construct a sentence , Make all the words in the sentence in the dictionary . In any order Go back to all these possible sentences .

Be careful ： The same word in the dictionary may be repeated many times in segments .

 

Example 1：

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

Example 2：

 Input :s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
 Output :["pine apple pen apple","pineapple pen apple","pine applepen apple"]
 explain :  Note that you can reuse the words in the dictionary .

Example  3：

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

 

Tips ：

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s  and  wordDict[i]  Only lowercase letters
• wordDict  All strings in are Different

Method 1 ： State compression （ Binary violence enumeration ）

The maximum length of the string to be split is $20$, and $20\times 2^{20}=20,971,520$, Plus in many cases, it will soon break（ Unless the data of specially made card data ）, Therefore, the operation can be completed within the specified time .

When it comes to state compression , This problem is related to 131. Split palindrome string The solution is very similar .

And (https://leetcode.letmefly.xyz/2022/07/23/LeetCode 0131. Split palindrome string /)[https://leetcode.letmefly.xyz/2022/07/23/LeetCode%200131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2/] The solution is the same , First of all, we use $i$ Enumerate which subscript to cut .

The length is $n$ There are a total of $n-1$ A place to cut .

After use $j$ from $0$ To $n-1$, Look at this. $n-1$ Which of the three cutting positions actually cuts . Then compare the cut substring with the dictionary , See if it exists in the dictionary . If all substrings exist in dictionary , Then use spaces to connect all substrings in this cutting mode , And count in the answer .

• Time complexity $O(n\times 2^n)$, among $n$ Is the length of the string . The time complexity of binary state compression enumeration is $2^n$, For an enumeration ( Cutting method ), You need to determine whether each substring of this cutting method is in the dictionary , Time complexity $O(n)$（ The time complexity of hash table can be regarded as O(1)）
• Spatial complexity $O(m+n)$, among $m$ Is the number of all characters in the dictionary . Binary state compression is compared to recursive state compression , The advantage is that recursion is not required （ Therefore, there is no need to consume recursive space ）, The answer is not included in the complexity of the algorithm , Therefore, the space complexity outside the dictionary is only the additional space required for a single enumeration $O(n)$

AC Code

C++

#define judge(thisWord) \ if (!st.count(thisWord))\ goto loop;\ thisBreak.push_back(thisWord);

class Solution {
    
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
    
        vector<string> ans;
        unordered_set<string> st;
        for (string& s : wordDict) {
    
            st.insert(s);
        }
        int n = s.size() - 1;
        for (int i = 0; i < (1 << n); i++) {
    
            vector<string> thisBreak;
            string toInsert;
            string thisWord;

            int last = 0;
            for (int j = 0; j < n; j++) {
    
                if (i & (1 << j)) {
    
                    thisWord = s.substr(last, j - last + 1);
                    judge(thisWord);
                    last = j + 1;
                }
            }
            thisWord = s.substr(last, s.size() - last);
            judge(thisWord);

            for (int i = 0; i < thisBreak.size(); i++) {
    
                if (i)
                    toInsert += ' ';
                toInsert += thisBreak[i];
            }
            ans.push_back(toInsert);
            loop:;
        }
        return ans;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/126016024