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".
方法一：
DFS，
start已知，当start超过str长度时，说明全部字符串都能找到了。。
小数据可过，大数据时超时
| Last executed input: | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"] |
1 class Solution { 2 public: 3 bool wordBreak(string s, unordered_set<string> &dict) 4 { 5 return wordBreak(s,0, dict); 6 } 7 8 bool wordBreak(string s, int start, unordered_set<string> & dict) 9 { 10 size_t size = s.size(); 11 if(size == 0) return false; 12 if(start >= size) 13 return true; 14 15 for( int i = start; i <size; i++) 16 { 17 string str = s.substr(start, i-start+1); 18 if(dict.find(str) != dict.end()) 19 { 20 if(wordBreak(s,i+1, dict)) 21 return true; 22 } 23 24 } 25 return false; 26 } 27 };
[LeetCode] Word Break,布布扣,bubuko.com
原文：http://www.cnblogs.com/diegodu/p/3830038.html