给你一个字符串 s,请你对 s 的子串进行检测。
每次检测,待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right],并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为 true,否则结果为 false。
返回答案数组 answer[],其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
注意:在替换时,子串中的每个字母都必须作为 独立的 项进行计数,也就是说,如果 s[left..right] = "aaa" 且 k = 2,我们只能替换其中的两个字母。(另外,任何检测都不会修改原始字符串 s,可以认为每次检测都是独立的)
示例:
输入:s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出:[true,false,false,true,true]
解释:
queries[0] : 子串 = "d",回文。
queries[1] : 子串 = "bc",不是回文。
queries[2] : 子串 = "abcd",只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd",可以变成回文的 "abba"。 也可以变成 "baab",先重新排序变成 "bacd",然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda",可以变成回文的 "abcba"。
提示:
1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/can-make-palindrome-from-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
有一个坑需要注意,即:子字符串中的所有字符的顺序是可变的,所以不能使用双指针来判断。
可以利用前缀和来判断一个字符串是否可以改成一个回文串(若一个字符串可以构成回文串,那么它所有的子字符两两互抵后,只会剩余一个或没有子字符)
可以利用数组来存储前缀和。
优化优化,由于只包含 26 个英文字符,所以也可以直接利用一个 int 数字来存储,使用位运算。
优化前版本:
class Solution { public List<Boolean> canMakePaliQueries(String s, int[][] queries) { List<Boolean> list = new ArrayList<>(); int len = s.length(); boolean[][] arr = new boolean[len + 1][26]; for (int i = 1; i < len + 1; i++) { arr[i] = Arrays.copyOf(arr[i - 1], 26); int tem = s.charAt(i - 1) - 'a'; arr[i][s.charAt(i - 1) - 'a'] ^= true; } for (int[] query : queries) { boolean[] tem1 = Arrays.copyOf(arr[query[0]], 26); boolean[] tem2 = Arrays.copyOf(arr[query[1] + 1], 26); for (int i = 0; i < 26; i++) { tem1[i] ^= tem2[i]; } int count = 0; for (boolean bol : tem1) { if (bol) { count ++; } } list.add((count >> 1) <= query[2]); } return list; } }
class Solution { public List<Boolean> canMakePaliQueries (String s, int[][] queries) { List<Boolean> list = new ArrayList<>(); int len = s.length(); int[] arr1 = new int[len + 1]; for (int i = 1; i < len + 1; i++) { int index = 1 << (s.charAt(i - 1) - 'a'); arr1[i] = arr1[i - 1] ^ index; } for (int[] query : queries) { int tem1 = arr1[query[0]]; int tem2 = arr1[query[1] + 1]; tem1 ^= tem2; int count = 0; while (tem1 > 0) { if ((tem1 & 1) == 1) { count++; } tem1 >>= 1; } list.add((count >> 1) <= query[2]); } return list; } }
还是有点慢,把求 tem1 中有多少个 1 的循环优化优化:
class Solution { public List<Boolean> canMakePaliQueries (String s, int[][] queries) { List<Boolean> list = new ArrayList<>(); int len = s.length(); int[] arr1 = new int[len + 1]; for (int i = 1; i < len + 1; i++) { int index = 1 << (s.charAt(i - 1) - 'a'); arr1[i] = arr1[i - 1] ^ index; } for (int[] query : queries) { int tem1 = arr1[query[0]]; int tem2 = arr1[query[1] + 1]; tem1 ^= tem2; // 调用库函数 int count = Integer.bitCount(tem1);; // int count = 0; // 官解方法: // while (tem1 > 0) { // tem1 &= tem1 - 1; // count++; // } // 之前的方法 // while (tem1 > 0) { // if ((tem1 & 1) == 1) { // count++; // } // tem1 >>= 1; // } list.add((count >> 1) <= query[2]); } return list; } }
标签:1177,力扣,子串,tem1,int,len,---,queries,回文 From: https://www.cnblogs.com/allWu/p/17484202.html