基本思想是使用回溯法,回溯法都可以将问题划分为一个解空间树:假设字符串s为"aab",那么我们可以使用深度优先搜索去构建解空间树:
dfs遍历出来的第一个序列是[a, a, b],显然该序列都是回文子串,接着回溯,遍历下一个序列,为[a, ab],不是回文子串,去除…如此往下遍历,将符合要求的序列加入到结果集res中,直到遍历整个解空间树
此题的重要思想有两个:
Java中的List变量存储的是List的地址,而非List本身,因此可以构建一个path列表,用于存储当前已经遍历的序列,当dfs向下遍历的时候则将新遍历的字符串加入path中;当向上回溯的时候,可以将path中的最后一个元素remove掉,从而恢复到上一个遍历状态
class Solution {public List<String> path = new ArrayList<>();public List<List<String>> result = new ArrayList();public void f(String str, int start){if (start >= str.length()){// 防止深复制导致的将List地址存入result,需要新建Listresult.add(new ArrayList<>(path));}for (int i = start; i < str.length(); i++) {if (isPalindrome(str, start, i)){path.add(str.substring(start, i+1));}elsecontinue;f(str, i+1);path.remove(path.size()-1); // 回溯}}public boolean isPalindrome(String s,int start,int end){//start从左到右,end从右到左,判断前后是否一致for(int i=start,j=end;i<j;i++,j--){if(s.charAt(i)!=s.charAt(j)){return false;}}return true;}public String[][] partition(String s) {f(s, 0);int rows = result.size();String[][] ret = new String[rows][];for (int i = 0; i < rows; ++i) {int cols = result.get(i).size();ret[i] = new String[cols];for (int j = 0; j < cols; ++j) {ret[i][j] = result.get(i).get(j);}}return ret;}
}