我在一個網站上發現了以下問題。
A wonderful string is a string where at most one letter appears an odd number of times.
For example, "ccjjc" and "abab" are wonderful, but "ab" is not.
Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.
A substring is a contiguous sequence of characters in a string.
Example 1 :
Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are a , b , a(last character) , aba.
我試圖解決它。我實作了一個 O(n^2) 解決方案（n 是輸入字串長度）。但是預期的時間復雜度是 O(n)。我無法在 O(n) 中解決它。我找到了以下解決方案，但無法理解。你能幫我理解下面這個問題的 O(n) 解決方案或想出一個 O(n) 解決方案嗎？我的 O(N^2) 方法 - 對于每個子字串檢查它是否最多有一個奇數計數字符。可以使用 10 個字符的陣列在 O(1) 時間內完成此檢查。
class Solution {
public:
long long wonderfulSubstrings(string str) {
long long ans=0;
int idx=0; long long xorsum=0;
unordered_map<long long,long long>mp;
mp[xorsum] ;
while(idx<str.length()){
xorsum=xorsum^(1<<(str[idx]-'a'));
// if xor is repeating it means it is having even ouccrences of all elements
// after the previos ouccerence of xor.
if(mp.find(xorsum)!=mp.end())
ans =mp[xorsum];
mp[xorsum] ;
// if xor will have at most 1 odd character than check by xoring with (a to j)
// check correspondingly in the map
for(int i=0;i<10;i ){
long long temp=xorsum;
temp=temp^(1<<i);
if(mp.find(temp)!=mp.end())
ans =mp[temp];
}
idx ;
}
return ans;
}
};
uj5u.com熱心網友回復：
代碼中有兩個主要的演算法技巧，位掩碼和前綴和，如果您以前從未見過它們，可能會感到困惑。我們先來看看這個問題是如何從概念上解決的。
對于字串 S 的任何子字串，我們想要計算 10 個可能字母中的每一個出現的次數，并詢問每個數字是偶數還是奇數。
例如，對于一個子串s = accjjc，我們可以將其概括為：odd# a, even# b,odd# c, even# d, even# e, even# f, even# g, even# h, even# i, even #j。這有點長，所以我們可以用一個位掩碼來總結它：對于每個字母 aj，1如果計數是奇數，或者0如果計數是偶數，就輸入 a 。這為我們提供了一個 10 位二進制字串，1010000000用于我們的示例。
您可以將其視為普通整數（或 long long，取決于整數的表示方式）。當我們看到另一個字符時，無論是偶數還是奇數，計數都會翻轉。在位掩碼上，這與翻轉單個位或 XOR 操作相同。如果我們添加另一個 'a'，我們可以通過將它與數字異或來更新位掩碼以從 'even# a' 開始1000000000。
我們想計算最多一個字符數是奇數的子串的數量。這與計算位掩碼最多為 1 的子串的數量相同1。有 11 個這樣的位掩碼：十個零的字串，每個字串1對于十個可能的點中的每一個都恰好有一個。如果將這些解釋為整數，則最后十個字串是 2 的前十次冪：1<<0, 1<<1, 1<<2, ... 1<<9。
現在，我們要及時計算所有子字串的位掩碼O(n)。首先，解決一個更簡單的問題：只計算所有前綴的位掩碼，并將這些計數存盤在哈希圖中。我們可以從一開始就保持運行位掩碼，并通過對應于信位的XOR進行更新，這樣做：xorsum=xorsum^(1<<(str[idx]-'a'))。這顯然可以在O(n)一次通過字串的時間傳遞中完成。
我們如何獲得任意子串的計數？答案是prefix-sums：任何子串中的字母數都可以表示為兩個前綴數的不同。例如，使用s = accjjc，假設我們想要與子字串 'jj' 對應的位掩碼。這個子串可以寫成兩個前綴的差：'jj' = 'accjj' - 'acc'.
同樣，我們要減去兩個前綴字串的計數。然而，我們只有位掩碼告訴我們每個字母的頻率是偶數還是奇數。在位掩碼的算術中，我們將每個位置 mod 2，因此坐標減法變為 XOR。
這意味著counts(jj) = counts(accjj) - counts(acc)變成
bitmask(jj) = bitmask(accjj) ^ bitmask(acc).
還有一個問題：我描述的演算法仍然是二次的。如果在每個前綴處，我們迭代所有先前的前綴位掩碼并檢查我們的掩碼是否與舊掩碼異或是 11 個目標位掩碼之一，我們仍然有二次運行時間。相反，您可以使用 XOR 是它自己的逆這一事實：如果a ^ b = c，則b = a ^ c。因此，不是使用舊的前綴掩碼進行異或運算，而是與 11 個目標掩碼進行異或并添加我們看到該掩碼的ans =mp[xorsum]次數：計算以我們當前索引結尾的子串，其位掩碼為xorsum ^ 0000000000 = xorsum。之后的回圈計算位掩碼是十個目標位掩碼之一的子串。最后，您只需要添加您的當前前綴掩碼來更新計數：mp[xorsum] 。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/329070.html
上一篇：為無向環狀序列創建唯一識別符號