140. Word Break II

问题:

给定一个字符串,和一个字典,将字符串切分后,每部分都是字典中字符串,求所有切分可能。

Example 1:
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

  

解法:Backtracking(回溯算法)DFS(深度优先搜索)

简单的回溯,会超时。

  • path:到当前位置截止,切分的结果。
  • opt:从当前位置,到n个字符所得字符串在字典中,则为符合条件选择。加入path。
  • 结束条件:当前位置=s.size。将path加入res。

代码参考:

 1 class Solution {
 2 public:
 3     void backtrack(vector<string>& res, string path, int pos, string s, unordered_set<string>& wordSet) {
 4         if(pos == s.size()) {
 5             path.pop_back();
 6             res.push_back(path);
 7             return;
 8         }
 9         for(int i=pos+1; i<=s.size(); i++) {
10             string tmp = s.substr(pos, i-pos);
11             if(wordSet.count(tmp)!=0) {
12                 backtrack(res, path+tmp+" ", i, s, wordSet);
13             }
14         }
15         return;
16     }
17     vector<string> wordBreak(string s, vector<string>& wordDict) {
18         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
19         vector<string> res;
20         string path;
21         backtrack(res, path, 0, s, wordSet);
22         return res;
23     }
24 };

 

DFS:

递归函数:对每个子字符串,返回要求的所有切分可能。vector<string> res

♻️ 优化方法:在递归中,可能出现重复字符串的求解,因此,使用map,对结果进行保存,每次递归,先check是否已经求解过该字符串s,有的话,之间返回map[s]

1.每次将所求字符串拆分为:尾部字符串endstr,和头部字符串headstr

2.首先,如果尾部字符串=本字符串全部,刚好在字典中,则res+={【endstr】}

3.for 尾部字符串:i~size(i:0~size-1)

        subres = 余下头部字符串 headstr去求递归。

        res += 【每个subres + “ ” + endstr】

4.将当前res存入map,map[s]=res

返回res。

 

代码参考:

 1 class Solution {
 2 public:
 3     vector<string> DFS(string s, unordered_map<string, vector<string>>& m, unordered_set<string>& wordSet) {
 4         if(m.count(s)) return m[s];
 5         vector<string> res;
 6         if(wordSet.count(s)) {
 7             res.push_back(s);
 8         }
 9         for(int i=0; i<s.size(); i++) {
10             string endstr = s.substr(i);
11             if(wordSet.count(endstr)) {
12                 string headstr = s.substr(0, i);
13                 vector<string> subres = DFS(headstr, m, wordSet);
14                 for(string path: subres) {
15                     res.push_back(path+" "+endstr);
16                 }
17             }
18         }
19         m[s] = res;
20         return res;
21     }
22     vector<string> wordBreak(string s, vector<string>& wordDict) {
23         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
24         unordered_map<string, vector<string>> m;
25         vector<string> res;
26         res = DFS(s, m, wordSet);
27         return res;
28     }
29 };

 

上一篇:力扣-12.18-139


下一篇:Word Break(C++单词拆分)