题解 | #训练聪明的牛#

知识点

动态规划

思路

用一个集合来存储所有单词，然后在s中枚举i~j位，并进行查找，找得到就把前j位标记为可以匹配，找不到的话肯定匹配不了了，答案为false 最后输出为dp[s.size()]

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param wordDict string字符串vector 
     * @return bool布尔型
     */
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string>st;
       for(auto v:wordDict)st.insert(v);
       vector<bool>dp(s.size()+1,false);
       dp[0]=true;
       for(int i=0;i<dp.size();i++)
       {
        for(int j=0;j<i;j++)
        {
            if(dp[j]&&st.find(s.substr(j,i-j))!=st.end())
            {
                dp[i]=true;
                break;
            }
        }
       }
return dp[s.size()];
        
    }
};