Description
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.
Examples
Example 1:
Input: s = “aab”
Output: [[“a”,“a”,“b”],[“aa”,“b”]]
Example 2:
Input: s = “a”
Output: [[“a”]]
思路
是一个backtrack的思路，discussion里面讲的很好，我直接一个偷图
可以通过识别左半部分是否为回文进行适当剪枝
backtrack的写法还是要靠熟能生巧，多写写就能记住了！
代码
class Solution {
public boolean isPalin(String s, int start, int end) {
while(start <= end) {
if (s.charAt(start) != s.charAt(end))
return false;
start ++;
end --;
}
return true;
}
public void recursive(String s, int startIndex, List<String> currPath, List<List<String>> answer) {
if (startIndex == s.length())
answer.add(new ArrayList<>(currPath));
for (int i = startIndex; i < s.length(); i++) {
if (isPalin(s, startIndex, i)){
currPath.add(s.substring(startIndex, i + 1));
recursive(s, i + 1, currPath, answer);
currPath.remove(currPath.size() - 1);
}
}
}
public List<List<String>> partition(String s) {
List<String> currPath = new ArrayList<>();
List<List<String>> answer = new ArrayList<>();
recursive(s, 0, currPath, answer);
return answer;
}
}
