Leetcode 0139. word splitting

【LetMeFly】139. Word splitting

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

Give you a string s And a list of strings wordDict As a dictionary . Please judge whether you can use the words in the dictionary to splice s .

Be careful ： It is not required to use all the words in the dictionary , And the words in the dictionary can be reused .

 

Example 1：

 Input : s = "leetcode", wordDict = ["leet", "code"]
 Output : true
 explain :  return  true  because  "leetcode"  Can be  "leet"  and  "code"  Stitching into .

Example 2：

 Input : s = "applepenapple", wordDict = ["apple", "pen"]
 Output : true
 explain :  return  true  because  "applepenapple"  Can be  "apple" "pen" "apple"  Stitching into .
      Be careful , You can reuse the words in the dictionary .

Example 3：

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

 

Tips ：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] Only lowercase letters
• wordDict All the strings in Different from each other

Method 1 ：dp

use $dp[i]$ Represents the beginning of a string $i$ Can the letters be spliced from the words in the dictionary .

Initial value dp[0] = true

use $n$ Represents the length of the string to be spliced

First dimensional cycle $i$ from $1$ To $n$, Judge the front of the string to be spliced in turn $i$ Can letters be spliced .

2D cycle $j$ from $0$ To $i-1$, Judge in turn front i Letters Whether it can be determined by Verified front that can be spliced j Letters and Exist in the dictionary from The first j One to the first i Letters The words that make up Splicing into .

If dp[j]==true also Substring of the original string [j, i] In the dictionary , Just put dp[i] Marked as true

• Time complexity $O(n^2)$
• Spatial complexity $O(n)$

AC Code

C++

class Solution {
    
public:
    bool wordBreak(string s, vector<string>& wordDict) {
    
        unordered_set<string> se;
        for (string& s : wordDict) {
    
            se.insert(s);
        }
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
    
            for (int j = 0; j < i; j++) {
    
                if (dp[j] && se.count(s.substr(j, i - j))) {
    
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

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/125991942