东莞网站优化是什么,成都旅游网站建设地址,注册app,营销培训总结题目#xff1a;
给你一个字符串 s 和一个整数 k #xff0c;请你将 s 分成 k 个 子字符串 #xff0c;使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数#xff0c;表示需要修改的 最少 字符数目。
注意#xff1a;
如果一个字符串从左往…题目
给你一个字符串 s 和一个整数 k 请你将 s 分成 k 个 子字符串 使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数表示需要修改的 最少 字符数目。
注意
如果一个字符串从左往右和从右往左读是一样的那么它是一个 回文串 。 如果长度为 len 的字符串存在一个满足 1 d len 的正整数 d len % d 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 那么我们说这个字符串是 半回文串 。比方说 “aa” “aba” “adbgad” 和 “abab” 都是 半回文串 而 “a” “ab” 和 “abca” 不是。 子字符串 指的是一个字符串中一段连续的字符序列。
示例 1
输入s “abcac”, k 2 输出1 解释我们可以将 s 分成子字符串 “ab” 和 “cac” 。子字符串 “cac” 已经是半回文串。如果我们将 “ab” 变成 “aa” 它也会变成一个 d 1 的半回文串。 该方案是将 s 分成 2 个子字符串的前提下得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。 示例 2:
输入s “abcdef”, k 2 输出2 解释我们可以将 s 分成子字符串 “abc” 和 “def” 。子字符串 “abc” 和 “def” 都需要修改一个字符得到半回文串所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。 该方案是将 s 分成 2 个子字符串的前提下得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。 示例 3
输入s “aabbaa”, k 3 输出0 解释我们可以将 s 分成子字符串 “aa” “bb” 和 “aa” 。 字符串 “aa” 和 “bb” 都已经是半回文串了。所以答案为 0 。
提示
2 s.length 200 1 k s.length / 2 s 只包含小写英文字母。
java代码
class Solution {char[] chars;int[][] dps;int[][] checks;public int minimumChanges(String s, int k) {this.chars s.toCharArray();final int n chars.length;this.dps new int[n][k 1];this.checks new int[n][n];return dp(0, k) - k;}private int checkD(int head, int tail, int d) {final int length tail - head 1;int res 0;for (int x 0; x d; x) {for (int left head x, right left length - d; left right; left d, right - d) {if (chars[left] ! chars[right]) res;}}return res;}private int check(int head, int tail) {if (checks[head][tail] 0) return checks[head][tail];int length tail - head 1;int sq (int)Math.sqrt(length);int best checkD(head, tail, 1);for (int d 2; d sq; d) {if (length % d 0) continue;best Math.min(best, checkD(head, tail, d));best Math.min(best, checkD(head, tail, length / d));}return checks[head][tail] best 1;}private int dp(int head, int k) {if (k 1) return check(head, chars.length - 1);if (dps[head][k] 0) return dps[head][k];final int end chars.length - (k - 1) * 2;int best Integer.MAX_VALUE;for (int tail head 1; tail end; tail) {int res check(head, tail) dp(tail 1, k - 1);best Math.min(best, res);}return dps[head][k] best;}
}
