转载

word-break

word-break

题目描述

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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

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

思想

动态规划是最好的解决办法

依次分析是s[0-1], s[0-2], s[0-3], ..s[size-1]是否是word sentence

前面的结果后面的计算能直接用,这就是动态规划

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
         vector<string> sb;

        if(s.size() == 0) return false;
        if(dict.size() == 0) return false;

        map<int, bool> M;

        for(int i = 0; i < s.size(); i++) {
            for(int j = 0; j < s.size(); j++) {
                if(j > i) break;
                else if(i == j) {
                    if(dict.count(s.substr(0, i+1)) > 0)  M[i] = true;
                }   
                else {
                    if(M[j] == true && dict.count(s.substr(j+1, i-j)) > 0) {
                        M[i] = true;
                    }
                }
            }
            if(M.count(i) <= 0) M[i] = false;
        }
        return M[s.size()-1];
    }
};
正文到此结束
本文目录