lintcode-单词切分

C++版

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
动态规划的本质：根据已知结论推理未知结论

class Solution {
public:
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    bool wordBreak(string s, unordered_set<string> &dict)
    {
        if(s.size() == 0 && dict.size() == 0)
            return true;
        if(s.size() == 0 || dict.size() == 0)
            return false;
    
        int len = (int)s.size();
        bool * dp = new bool[len+1];
        dp[0] = true;
    
        for(int i = 0; i <= len; ++i)
        {
            if(!dp[i])
                continue;
            unordered_set<string>::iterator it;
            for(it = dict.begin(); it != dict.end(); ++it)
            {
                string value = *it;
                int lv = (int)value.size();
                if(i+lv > len)
                    continue;
                string last = s.substr(i, lv);
                if(last == value)
                    dp[i+lv] = true;
            }
        }
    
        return dp[len];
    }
};

Java版

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here   
        if((s==null ||s.length() ==0) && (dict == null || dict.size()==0))
            return true;
        return wordBreak(s,dict,0);
    }
     public boolean wordBreak(String s,Set<String> dict,int start){
        boolean dp[] = new boolean[s.length() + 1];
        dp[0] = true;//初始值
        for(int i = 0;i<s.length();i++){
            if(!dp[i])
                continue;
            for(String t:dict){
                int len = t.length();
                int end = i+ len;
                if(end > s.length())
                    continue;
                if(s.substring(i,end).equals(t)){
                    dp[end] = true;
                }
            }
        }
        return dp[s.length()];
    }
    
}