Leetcode--Word Break - c++编程基础

Problem Description:

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".

分析：

这个题目最容易想到的是利用递归，不断地拆分出在字典中的单词，然后递归判断后缀是否能被拆分，后来想着利用利用字典中的单词最大最小长度提高效率，结果还是超时，具体代码如下：

class Solution {
public:
    int minlen,maxlen;
    void findlen(unordered_set
  
    &dict)
    {
        unordered_set
   
    ::iterator iter=dict.begin(); minlen=(*iter).length(); maxlen=(*iter).length(); for(iter=dict.begin();iter!=dict.end();++iter) { if((*iter).length()
    
     maxlen) maxlen=(*iter).length(); } } bool wordcontain(string s, unordered_set
     
       &dict,int begin) { if(begin==s.length()) return true; for(int i=minlen;i<=maxlen;++i) { if((begin+i)>s.length()) continue; if(dict.find(s.substr(begin,i))!=dict.end()) if(wordcontain(s,dict,begin+i)) return true; } return false; } bool wordBreak(string s, unordered_set
      
        &dict) { if(s.empty()||dict.empty()) return false; findlen(dict); return wordcontain(s,dict,0); } };

Submission Result: Time Limit Exceeded

Last executed input:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

然后在discuss区看了一些讨论，发现应该用动态规划来实现，利用一个一维bool数组记录子串是否可被拆分，减少了重复判断子串的次数，效率明显提高。代码如下：

class Solution {
public:

    bool wordBreak(string s, unordered_set
  
    &dict) {
        if(s.empty()||dict.empty())
            return false;
        int len=s.size();
        vector
   
     flag(len+1,false); flag[0]=true; for(int i=1;i<=len;++i) for(int j=0;j