1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
private:
vector<vector<string>> result;
vector<string> path;
public:
bool isReStr(const string& str){
int left = 0;
int right = str.size() - 1;
while(left <= right){
if(str[left] != str[right]){
return false;
}
left++;
right--;
}
return true;
}
void backtrace(string s,int start){
if(start == s.size()){
result.push_back(path);
return;
}
for(int i = start; i < s.size(); i++){
string data = s.substr(start,i - start + 1);
if(isReStr(data)){
path.push_back(data);
backtrace(s,i + 1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
backtrace(s,0);
return result;
}
};
|
这道题没有能够做出来，尽管对于切割有些思路了，但是对于 substr 方法有些误解（后面详细谈一谈它的用法），导致实际返回的容器中有很多重复项。
再有就是对 s.substr(start,i - start + 1) 语句没有理解透彻，这是用来切割可能要加入到路径中的字符。首先 start 指明要切割字符串的起始地址，而 substr 的第二个参数要填写切割的长度，由于 i 代表的是指向当前字符串的终止位置（不一定就是字符串的最后位置），且最初 i = start，那么至少要切割一个字符，因此是 i - start + 1。由于切割的字符串得是回文字符串才会再次进入循环， 否则一直不断增加切割长度，直到出现回文字符串，否则退出当前循环，这也是为什么要 i - start + 1，假定这次不满足，下一次循环中 i 会自增，而 start 保持不变，也就实现继续切割。
再一个重点就是 backtrace(s,i + 1) ，我们注意看传递进去的第二个参数的含义，即 切割字符串的起始位置，你可能会误写成 start + 1，但实际上是 i + 1，因为 i 指向被切割字符的最后的位置，所以下一个被切割字符串的位置是 i + 1。因为 [start,i] 区间内的字符串已经被处理了，所以下一次切割的地址是 i + 1，而不是 start + 1。
1
| string substr (size_t pos = 0, size_t len = npos) const;
|
pos 代表切割字符串的起始地址
len 代表从指定起始地址开始切割的长度
1
2
3
4
5
6
7
8
9
10
| string name = "aahswl";
cout << name.substr(0, 2) <<endl;
cout << name.substr(4, 3) << endl;
|
主要强调第二个切割，明明指定长度加上起始位置已经超出 name 字符串的长度，但还是切割成功，所以即便只能切割到最后两个字符串了（因为按理我们要切割长度为三的字符串），这也是切割成功，返回字符串 wl。
如果 len 等于字符串长度，返回空字符串；如果 len 大于 字符串长度，抛出异常。
