Posted on 2014-01-14 03:13
Uriel 閱讀(305)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
LeetCode
這題是Word Break的加強(qiáng)版，要輸出所有可能的單詞組合，于是想到用DFS，string操作還是不熟啊，搞到吐血之后，還是參照了解題報(bào)告的寫(xiě)法：
1 class Solution {
2 public:
3 int max_len, min_len;
4 vector<string> res;
5 vector<string> tp_res;
6
7 void save_sentence() {
8 string s = "";
9 for(int i = tp_res.size() - 1; i >= 0; --i) s += tp_res[i] + string(" ");
10 s.pop_back();
11 res.push_back(s);
12 }
13
14 void sov(string s, unordered_set<string> &dic) {
15 int len = s.size();
16 if(!len) {
17 save_sentence();
18 return;
19 }
20 for(int i = min_len; i <= min(max_len, len); ++i) {
21 string tp = s.substr(len - i);
22 if(dic.find(tp) != dic.end()) {
23 tp_res.push_back(tp);
24 sov(s.substr(0, len - i), dic);
25 tp_res.pop_back();
26 }
27 }
28 }
29
30 vector<string> wordBreak(string s, unordered_set<string> &dic) {
31 res.clear();
32 min_len = 100000, max_len = 0;
33 unordered_set<string>::iterator it;
34 for(it = dic.begin(); it != dic.end(); ++it) {
35 max_len = max_len > it->size() ? max_len : it->size();
36 min_len = min_len < it->size() ? min_len : it->size();
37 }
38 sov(s, dic);
39 return res;
40 }
41 };