代码随想录算法训练营第四十六天| 139 单词拆分

2023-12-13 05:57:40

?目录

139 单词拆分

139 单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool>dp(s.size() + 1);//长度为i的字符串时能否成功拆分
        unordered_set<string>set(wordDict.begin(),wordDict.end());
        dp[0] = true;
        for(int i = 1;i <= s.size();i++){
            for(int j = 0;j < i;j++){
                string word = s.substr(j,i - j);//接下来在set中寻找等于word的值
                if(set.find(word) != set.end() && dp[j])dp[i] = true;
            }
        }
        return dp[s.size()];
    }
};

时间复杂度O(n^3)n是substr的长度

空间复杂度O(n)

文章来源:https://blog.csdn.net/m0_72832574/article/details/134900696
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。