讨论/《算法面试题汇总》 - 单词拆分/
《算法面试题汇总》 - 单词拆分
共 7 个回复

回溯有个用例超时
加一句:
if(s.length()>50)
return false;
就过了,哈哈哈哈哈哈

5
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False for _ in range(len(s) + 1)]
        maxlen = max([len(word) for word in wordDict])
        dp[0] = True
        for i in range(1, len(s) + 1):
            for j in range(max(0, i - maxlen), i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
        return dp[len(s)]
1

老哥,稳

好家伙,活生生凑了个双dp才做出来,sort那行代码可以优化成for找到最小的长度,懒得改了

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int m = wordDict.size();
        int n = s.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        vector<int> temp(n+1,0);
        sort(wordDict.begin(),wordDict.end(),[&](string x ,string y){
            if(x.size()<y.size()) return true;
            else return false;
        });
        dp[0][0] = temp[0] = true;
        if(wordDict[0] == s.substr(0,wordDict[0].size())){
            dp[wordDict[0].size()][1] = true;
        }
        for(int i = wordDict[0].size();i<= n;++i){
            for(int j = 1;j<=m ;++j){
                int len = wordDict[j-1].size();
                if(dp[i][j-1]){
                    temp[i] = true;
                    dp[i][j] = true;
                }
                if(len<=i&&temp[i-len]&&s.substr(i-len,len) == wordDict[j-1]){
                    dp[i][j] = true;
                    temp[i] = true;
                }
            }
        }
        return dp[n][m];
    }
};

奇技淫巧(x

我没看懂,然后去题库里面看了讨论,有大佬写了解答,标注一下给后来的小伙伴
【笔记】动态规划 dp[i]表示字符串s的前i个字符能否拆分成wordDict

dfs 超时了
class Solution {
public:
    unordered_map<string, int> mp;
    bool myHelp(string s, int start){
        if(start > s.length() - 1){
            return true;
        }
        for(int i = start; i < s.length(); i++){
            if(mp.find(s.substr(start, i - start + 1)) != mp.end() && myHelp(s, i + 1)){
                return true;
            }
        }
        return  false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        for(auto i : wordDict){
            mp[i]++;
        }
        return myHelp(s, 0);
    }
};