分割回文串例题-区分组合回溯与最优动态规划

131.分割回文串

class Solution {List<List<String>> result=new ArrayList<>();int n;public List<List<String>> partition(String s) {n=s.length();dfs(0,new ArrayList<>(),"",s);return result;}public void dfs(int i,List<String> l,String prefix,String s){if (i==n){//判断list里面每个元素是否是回文串for (String item:l){String newStr = new StringBuilder(item).reverse().toString();if (!newStr.equals(item)){return;}}//注意 这里要拷贝一份新的result.add(new ArrayList<>(l));return;}//当前元素后不分割if (i<n-1){dfs(i+1,l,prefix+s.substring(i,i+1),s);}System.out.println(i);//当前元素后分割l.add(prefix+s.substring(i,i+1));dfs(i+1,l,"",s);l.remove(l.size()-1);}
}

132.分割回文串2

class Solution {public int minCut(String S) {char[] s = S.toCharArray();int n = s.length;int[][] palMemo = new int[n][n];for (int[] row : palMemo) {Arrays.fill(row, -1); // -1 表示没有计算过}int[] dfsMemo = new int[n];Arrays.fill(dfsMemo, -1); // -1 表示没有计算过return dfs(n - 1, s, palMemo, dfsMemo);}private int dfs(int r, char[] s, int[][] palMemo, int[] dfsMemo) {if (isPalindrome(0, r, s, palMemo)) { // 已是回文串，无需分割return 0;}if (dfsMemo[r] != -1) { // 之前计算过return dfsMemo[r];}int res = Integer.MAX_VALUE;for (int l = 1; l <= r; l++) { // 枚举分割位置if (isPalindrome(l, r, s, palMemo)) {res = Math.min(res, dfs(l - 1, s, palMemo, dfsMemo) + 1); // 在 l-1 和 l 之间切一刀}}return dfsMemo[r] = res; // 记忆化}private boolean isPalindrome(int l, int r, char[] s, int[][] palMemo) {if (l >= r) {return true;}if (palMemo[l][r] != -1) { // 之前计算过return palMemo[l][r] == 1;}boolean res = s[l] == s[r] && isPalindrome(l + 1, r - 1, s, palMemo);palMemo[l][r] = res ? 1 : 0; // 记忆化return res;}
}