061分割回文串

分割回文串题目链接https://leetcode.cn/problems/palindrome-partitioning/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListListString partition(String s) { ListListString ans new ArrayList(); backtreack(s, 0, 1, new ArrayList(), ans, 0); return ans; } //last上一次分割的位置 cur当前分割的位置 public void backtreack(String s, int last, int cur, ListString output, ListListString ans, int sum){ System.out.println(cur); int sLen s.length(); if(cur sLen 1){ if(sum sLen){ ans.add(new ArrayList(output)); } return; } //分割 String left s.substring(last, cur); //left是回文串 if(valid(left)){ output.add(left); backtreack(s, cur, cur1, output, ans, sum cur - last); //回溯 output.remove(output.size() - 1); } //不分割 backtreack(s, last, cur1, output, ans, sum); } //判断字符串是否为回文串 public boolean valid(String str){ int l 0, r str.length() - 1; while(l r){ if(str.charAt(l) ! str.charAt(r)){ return false; } l; r--; } return true; }分析代码的时间复杂度为O(n^2 * 2^n)空间复杂度为O( n^2 )。解题思路每个位置分为分割和不分割两种情况假设当前位置为cur上一次分割的位置为last若s中[last,cur-1]的子串是回文字符串则当前位置可以考虑分割统计已经加入output的字符个数若分隔完s的最后一个位置判断output加入字符串的总个数是否与s的长度相等若相等则证明当前分割方法是一个可行的方法将其加入答案。看了官方题解后的解答//方法一回溯 动态规划预处理 //时间复杂度O(n*2^n)其中 n 是字符串 s 的长度。在最坏情况下s 包含 n 个完全相同的字符因此它的任意一种划分方法都满足要求。尽管动态规划预处理需要O(n^2)的时间但在渐进意义下小于O(n*2^n)因此可以忽略。 //空间复杂度O(n^2) boolean[][] f;//f[i][j]为true表示[i,j]为回文串 ListListString ans new ArrayList(); ListString output new ArrayList(); int n; public ListListString partition(String s) { n s.length(); f new boolean[n][n]; for(int i0; in; i){ Arrays.fill(f[i], true); } for(int in-1; i0; i--){ for(int ji1; jn; j){ f[i][j] s.charAt(i) s.charAt(j) f[i1][j-1]; } } dfs(s, 0); return ans; } public void dfs(String s, int cur){ if(cur n){ ans.add(new ArrayList(output)); return; } for(int icur; in; i){ if(f[cur][i]){ output.add(s.substring(cur, i1)); dfs(s, i1); output.remove(output.size() - 1); } } } //方法二回溯 记忆化搜索 //时间复杂度O(n*2^n)其中 n 是字符串 s 的长度。在最坏情况下s 包含 n 个完全相同的字符因此它的任意一种划分方法都满足要求。尽管动态规划预处理需要O(n^2)的时间但在渐进意义下小于O(n*2^n)因此可以忽略。 //空间复杂度O(n^2) int[][] f;//记忆化搜索中f[i][j] 0 表示未搜索1 表示是回文串-1 表示不是回文串 ListListString ans new ArrayList(); ListString output new ArrayList(); int n; public ListListString partition(String s) { n s.length(); f new int[n][n]; dfs(s, 0); return ans; } public void dfs(String s, int cur){ if(cur n){ ans.add(new ArrayList(output)); return; } for(int icur; in; i){ if(isPalindrome(s, cur, i) 1){ output.add(s.substring(cur, i1)); dfs(s, i1); output.remove(output.size() - 1); } } } // 记忆化搜索中f[i][j] 0 表示未搜索1 表示是回文串-1 表示不是回文串 public int isPalindrome(String s, int i, int j){ if(f[i][j] ! 0){ return f[i][j]; } if(i j){ f[i][j] 1; } else if(s.charAt(i) s.charAt(j)){ f[i][j] isPalindrome(s, i1, j-1); }else{ f[i][j] -1; } return f[i][j]; }分析​ 1、方法一的解题思路利用动态规划将字符串s的每个子串s[i,j] 是否为回文串预处理出来得到二维数组f的各个值f[i] [j]为true代表s[i,j]为回文串经过分析可以得到f的状态转移方程为​ f[i] [j] trueij​ f[i] [j] (s[i] s[j]) f[i1] [j-1]otherwise​ 然后我们从0位置开始递归寻找每种可行的分割方法假设递归到的当前位置为cur此时[0,cur-1]已经被分割成若干个回文串那么我们从cur开始遍历后续位置若[cur,i]为回文串则继续下一层递归下一层递归位置为i1即对每一个可以使得子串s[cur,i]为回文串的i都做一次分割然后继续递归判断剩下的[i,n-1]是否有可行的分割方法不断重复此操作直到字符串s遍历完。​ 2、方法二的解题思路与方法一的解题思路一致只是将判断s的每个子串s[i,j] 是否为回文串的方法由动态规划改为了记忆化搜索。​ 3、我的解答思路与官方解答的思路主要区别就在于判断子串是否为回文串的方法。总结本题主要考察判断一个字符串的任意子串是否为回文串的方法有两种判断方法分别为动态规划预处理和记忆化搜索。