Leetcode 139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

分析

动态规划

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
         vector<int> dp(s.size()+1,0);
         dp[0]=1;
         for(int i=0;i<s.size();i++)
             for(int j=i;j>=0;j--)
                 for(int k=0;k<wordDict.size();k++)
                     if(wordDict[k]==s.substr(j,i-j+1)&&dp[j]==1)
                        dp[i+1]=1;
        if(dp[s.size()]==1)
            return true;
        else
            return false;
    }
};