java:
class Solution {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return res;
}
public void backTracking(String s, int startIdx) {
if (startIdx == s.length()) {
res.add(new ArrayList<>(path));
return ;
}
for (int i = startIdx; i < s.length(); i++) {
if (!isParSubStr(s.substring(startIdx, i + 1)))
continue;
path.add(s.substring(startIdx, i + 1));//注!!substring是截至下一位
backTracking(s, i + 1);//注!!是i+1,不是startIdx + 1;
path.remove(path.size() - 1);
}
}
public boolean isParSubStr(String str) {
int i = 0, j = str.length() - 1;
while (i < j) {
if (str.charAt(i) != str.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}