LeetCode: Word Break [139]

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.length()==0)return false;
        vector<bool> canSegmented(s.length(), false);
        vector<int> segmentedIndex(1, -1);  //记录可被完整切分的位置
        //依次判定每个位置i上s[0-i]能够被完整切分
        for(int i=0; i<s.length(); i++){
            //根据以确定的可切分位来判断当前位
            for(int k=0; k<segmentedIndex.size(); k++){
                if(dict.find(s.substr(segmentedIndex[k]+1, i-segmentedIndex[k]))!=dict.end()){
                    canSegmented[i]=true;
                    segmentedIndex.push_back(i);
                    break;
                }
            }
        }
        return canSegmented[s.length()-1];
    }
};