leetcode 139. 单词拆分

分手后的思念是犯贱 2023-10-10 10:09 49阅读 0赞

**递归暴力超时**

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution { 
    public:
        bool wordBreak(string s, vector<string>& wordDict) { 
            if( s.size()==0){ 
                return true;
            }else{ 
                for(int i=0;i<wordDict.size();i++){ 
                    if( s.find( wordDict[i] ) == 0 ){ 
    
                        if( wordBreak( s.substr( wordDict[i].size() ),wordDict ) ){ 
                            return true;
                        }
                    }
                }
                return false;
            }
            return false;
        }
    };
    
    int main()
    { 
        Solution Solution1;
        vector<string> disc = { "a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
        string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        cout << Solution1.wordBreak(s,disc) << endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

**dp**  
**dp\[i\]表示从s\[0\]开始长度为i的子串是不是可以拆分**

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    class Solution { 
    public:
        bool wordBreak(string s, vector<string>& wordDict) { 
            vector<bool> dp(s.size()+1,0);
            dp[0] = 1;
            int i = 1;
            while( i <= s.size() ){ 
    
                if(dp[i-1]==1 ){ 
                    for(int j=0;j < wordDict.size();j++){ 
                        if(  s.find( wordDict[j],i-1) == i-1){ 
                            dp[ i + wordDict[j].size()-1 ] = 1;
                        }
                    }
                }
                i++;
    
            }
    
            return dp[ s.size() ];
    
        }
    };
    
    int main()
    { 
        Solution Solution1;
        vector<string> disc = { "a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
        string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        cout << Solution1.wordBreak(s,disc) << endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190924210419893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190924211603877.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3,size_16,color_FFFFFF,t_70