139. Word Break.md

题目

Word Break

思路

• 递归法会超时。每一步都将数组里的字串与目标子串相比较，更新标志指针。
• 递归+记忆数组，用一个vector存储"从该元素到达终点是否还有希望"，初始化默认为全true.
• 动态规划 用a[i]表示到该位置为止可以被字典构成，那么递推公式应该是 a[i]=a[j]&&子串中应该可以找到string(j,i];(j<i)

存疑：a[j]&&m.find(s.substr(j,i-j) 为什么是(j,i-j)不是(j+1,i-j)吗;

代码

• 递归，会超时

class Solution {
public:
    bool recur(size_t cur,string &s,vector<string>&vs，){
        if(cur==s.size()) return true;
        for(auto&p:vs){
            string tmp=s.substr(cur,p.size());
            if(tmp==p){
                 //cur += p.size();
			    if (recur(cur+p.size(), s, vs)) return true;
	    	}
        }
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> visit(s.size(),false);
        return recur(0,s,wordDict);
    }
};

• 递归+记忆化:内存和时间都超过了95%，可以看出记忆数组提升性能非常大。

class Solution {
public:
    bool recur(size_t cur,string &s,vector<string>&vs,vector<bool>& visit){
        if(cur==s.size()) return true;
        if(!visit[cur]) return false;
        for(auto&p:vs){
            string tmp=s.substr(cur,p.size());
            if(tmp==p){
                 //cur += p.size();
			    if (recur(cur+p.size(), s,vs, visit)) return true;
	    	}
        }
        visit[cur]=false;
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> visit(s.size()+1,true);
        return recur(0,s,wordDict,visit);
    }
};

• 动态规划:还是有提升空间的

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> a(s.size()+1,false);
        unordered_set<string> m(wordDict.begin(),wordDict.end());
        a[0]=true;
        
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<i;j++){
                if(a[j]&&m.find(s.substr(j,i-j))!=m.end()){
                    a[i]=true;
                    break;
                }
            }
        }
        return a[s.size()];
    }
};