LeetCode 139. Word Break 又一个优于网上博客的新解法 动态规划+二分


动态规划部分,参考网上博客就好,细想一下,每一次都需要搜索wordDict确定这个子串是否是一个单词,用二分优化这部分,在wordDict特别大的时候一定有奇效,m= len(wordDict),复杂度由)O(n^2*m),变为O(n^2*logm)~~
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if (s.size() == 0 || wordDict.size() == 0){
            return false;
        }
        
        sort(wordDict.begin(), wordDict.end());
        int dp[100000];
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        
        for (int i = 0; i <= s.size(); ++i){
            if(dp[i]){
                for (int j = i; j < s.size(); ++j){
                    string subWord = s.substr(i, j - i + 1);
                    if (binary_search(wordDict.begin(), wordDict.end(), subWord)){
                        dp[j + 1] = 1;
                    }
                }
            }
        }
        
        return dp[s.size()];
    }
};
已邀请:

要回复问题请先登录注册

返回顶部