毕设代做的网站,农产品信息网站建设方案,南沙滩网站建设,企业的做网站分割回文串 II 分割回文串 II动态规划 回文字符串 分割回文串 II 给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1#xff1a; 输入#xff1a;s “aab” 输出#xff1a;1 解释#xff1a;… 分割回文串 II 分割回文串 II动态规划 回文字符串 分割回文串 II 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1 输入s “aab” 输出1 解释只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2 输入s “a” 输出0 示例 3 输入s “ab” 输出1 提示 1 s.length 2000 s 仅由小写英文字母组成 动态规划 对于长度为n的字符串我们用[1,n]来表示。也就是下标从0开始。 我们首先先用动态规划的思想计算出字符串中有多少个回文字串。 我们用双指针的技巧一个指针卡住左边l一个指针卡住右边r。然后递归去计算[l,r]范围内是否是回文字符串。我们用boolean[l][r] 来标记l到r范围是不是回文串。 动态规划就是要去找到状态转移方程。 首先想到如果l r 只有一个元素肯定是回文串g[l][r] true; 如果r - l 1时说明只有两个长度那么只要l上字符等于r上的字符就说明是回文字符串。g[l][r] true; 然后是一般性考虑。如果l上字符等于r上的字符 ,并且g[l 1][r - 1]也是回文那么整个范围都是回文 因为可以得到状态转移方程。 g[l][r] r - l 1 || g[l 1][r - 1]; 然后计算回文分割的长度 我们定义f[r]为将[1,r] 这一段字符分割为若干回文串的最小分割次数那么最终答案为f[n]。 不失一般性的考虑f[r]如何转移 从「起点字符」到「第r 个字符」能形成回文串。那么最小分割次数为 0此时有f[r] 0 从「起点字符」到「第 r个字符」不能形成回文串。此时我们需要枚举左端点 l如果[l,r] 这一段是回文串的话那么有f[r] f[l - 1] 1 在 2中满足回文要求的左端点位置l 可能有很多个我们在所有方案中取一个最小的 即可。 代码演示 public int minCut(String s) {int n s.length();char[] cs s.toCharArray();// g[l][r] 代表 [l,r] 这一段是否为回文串boolean[][] g new boolean[n 1][n 1];for (int r 1; r n; r) {for (int l r; l 1; l--) {// 如果只有一个字符则[l,r]属于回文if (l r) {g[l][r] true;} else {// 在 l 和 r 字符相同的前提下if (cs[l - 1] cs[r - 1]) {// 如果 l 和 r 长度只有 2或者 [l1,r-1] 这一段满足回文则[l,r]属于回文if (r - l 1 || g[l 1][r - 1]) {g[l][r] true;}}}}}// f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数int[] f new int[n 1];for (int r 1; r n; r) {// 如果 [1,r] 满足回文不需要分割if (g[1][r]) {f[r] 0;} else {// 先设定一个最大分割次数r 个字符最多消耗 r - 1 次分割f[r] r - 1;// 在所有符合 [l,r] 回文的方案中取最小值for (int l 1; l r; l) {if (g[l][r]) f[r] Math.min(f[r], f[l - 1] 1);} }}return f[n];}回文字符串
leetcode131. 分割回文串
