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 <string> 2 #include <set> 3 #include <algorithm> 4 using namespace std; 5 class Solution { 6 public: 7 bool wordBreak(string s, unordered_set<string> &dict) { 8 unordered_set<string>::iterator iter; 9 string substr1,substr2; 10 substr1 = substr2 = s; 11 //short->long 12 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->short 25 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 };