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

字符匹配问题，值得注意的有一点：对一个字符从小到大找过没有匹配之后还要从大到小找一次，如果还是没有匹配才是真的没有匹配

testcase string s = "aaaaaaa", set<String> :{"aaa","aaaa"}就是这样的例子。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 class Solution { 6 public:     7     bool wordBreak(string s, unordered_set
        
          &dict) { 8         unordered_set
         
          ::iterator iter; 9         string substr1,substr2;10         substr1 = substr2 = s;11         //short->long12         for(int i = 1; i<= s.size();i++){13             substr1 = s.substr(0,i); 14             iter = dict.find(substr1);15             while(iter == dict.end()&& i < s.size()){16                 substr1 = s.substr(0,++i);17                 iter = dict.find(substr1);18             }19             if(iter == dict.end() && i == s.size())    break;20             s = s.substr(i);21             i = 0;22         }23         if(s.size() == 0)    return true;24         //long->short25         s = substr2;26         for(int i = s.size(); i > 0;i--){27             substr2 = s.substr(0,i); 28             iter = dict.find(substr2);29             while(iter == dict.end()&& i > 0){30                 substr2 = s.substr(0,--i);31                 iter = dict.find(substr2);32             }33             if(iter == dict.end() && i == 0)    break;34             s = s.substr(i);35             i = s.size()+1;36         }37         if(s.size() == 0)    return true;38         return false;39     }40 };