1. 題目

給你一個字符串 s，請你對 s 的子串進(jìn)行檢測。

每次檢測，待檢子串都可以表示為 queries[i] = [left, right, k]。我們可以 重新排列 子串 s[left], ..., s[right]，并從中選擇 最多 k 項替換成任何小寫英文字母。

如果在上述檢測過程中，子串可以變成回文形式的字符串，那么檢測結(jié)果為 true，否則結(jié)果為 false。

返回答案數(shù)組 answer[]，其中 answer[i] 是第 i 個待檢子串 queries[i] 的檢測結(jié)果。

注意：在替換時，子串中的每個字母都必須作為 獨立的 項進(jìn)行計數(shù)，也就是說，如果 s[left..right] = "aaa" 且 k = 2，我們只能替換其中的兩個字母。（另外，任何檢測都不會修改原始字符串 s，可以認(rèn)為每次檢測都是獨立的）

示例： 輸入：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.com/problems/can-make-palindrome-from-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 記錄到每個字符位置處的前綴字符計數(shù)
• 通過 r - (l-1) 得到區(qū)間 [ l, r ] 的字符計數(shù)
• 統(tǒng)計奇數(shù)字符出現(xiàn)的次數(shù)
• 區(qū)間長度為偶數(shù) odd-2*k <=0
• 區(qū)間長度為奇數(shù) odd-2*k <=1

class Solution { public:vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {int i, j, l, r, n = queries.size(), odd;vector<vector<int>> count(s.size(),vector<int>(26,0));vector<int> temp(26,0);vector<bool> ans(n);for(i = 0; i < s.size(); ++i){temp[s[i]-'a']++;count[i] = temp;//前綴字符計數(shù)}for(i = 0; i < n; ++i){l = queries[i][0];r = queries[i][1];temp = count[r];if(l-1>=0){for(j = 0; j < 26; ++j)temp[j] -= count[l-1][j];}odd = 0;for(j = 0; j < 26; ++j)if(temp[j]%2)odd++;if((r-l)%2)//長度偶數(shù)ans[i] = (odd-2*queries[i][2]<=0);elseans[i] = (odd-1-2*queries[i][2]<=0);}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1177. 构建回文串检测（前缀和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。