正文
131. Palindrome Partitioning(回文子串划分 深度优先)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Given a string
s
, partition
s
such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s .
For example, given
s
=
"aab"
,
Return
[
["aa","b"],
["a","a","b"]
]
解题思路
求所有答案,首先排除动态规划,应该是DFS (Palindrome Partitioning II 求个数才是动归)
- 遇到要求所有组合、可能、排列等解集的题目,一般都是DFS + backtracking
- 首先传入s="aab" path=[] res = [], 首先切割出"a"(然后是"aa" "aab" ...),然后判读它是不是回文串:
- 如果不是,直接跳过
- 如果是,则此时剩余的 s="ab", path += ["a"]
- 写入res的判断是,当s=""时,记录结果
class Solution {
private List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) { help(new ArrayList<>(), s, 0);
return res;
} private void help( List<String> temp, String s, int index){
if(index == s.length())
res.add(new ArrayList<>(temp));
else{
for(int i = index; i < s.length(); i++){
if(isPalindrome(s, index, i)){
temp.add(s.substring(index, i + 1));
help(temp, s, i + 1);
temp.remove(temp.size() - 1);
}
}
}
} public boolean isPalindrome(String s, int low, int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
}