推 oinishere: 大師 04/30 16:01
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/number-of-wonderful-substrings/description
: 1915. Number of Wonderful Substrings
: 給你一個包含小寫字母a~j的字串，如果一個子字串的所有字母只有一個字母出現奇數次
: 那麼他就是一個超讚字串，求出s裏面有幾個超讚子字串。
: 思路：
: 1.我們要判斷一個字串是不是超讚字串要檢查他的奇偶，我們可以用一個二進位數字表
: 示，奇數為1偶數為0，因為有10個 字母所以需要10位數的二進制就可以表示，狀
: 態初始化為0000000000 -> i = -1 (什麼都不加必定是偶數)
: 假設加入一個a狀態變成1000000000 -> i = 0
: 加入一個b狀態變成1100000000 -> i = 1
: 加入一個a狀態變成0100000000 -> i = 2
: 加入一個b狀態變成0000000000 -> i = 3
: ...
: 為了方便討論，後面我們稱二進位數字為"狀態"
: 2.如果 i 不同但是狀態相同(例如上面i=-1和i=3)，兩個"狀態"之間的字母必定只會出
: 現偶數次(奇數不可能相同)，所以：
: b ... [xxxxx] ... b
: 如果最後一個b的狀態等於前面的那個b，可以不斷地擴展會變成：
: b -> [中間必定是偶數] -> b -> [中間必定是偶數] -> b
: 因為這個特性，只要先前的狀態前面出現過，他就可以跟前面的狀態接在一起變成一
: 個新的超讚數字，就像是
: b => bb => bbb
: 這樣所以我們只要找有幾個b就好，找的過程又可以分成奇偶兩個case。
: 3.可以使用前綴和技巧求解，因為最多有2^10個狀態所以可以把map換成array
: 假定 cnt[x] 表示二進位x這個狀態的出現次數:
: (1) 任何數加上偶數，奇偶性不變。
: 同第二點所述，累加前面的 cnt[x] 總數(只要該狀態有出現過就一定可以累加)
: (2) 任何數加上奇數，奇數變偶數，偶數變奇數。
: 假設前面存在一個前綴字串 x 可和 word[i] 組成一個超讚字串，那麼必定滿足:
: x ^ word[i] = 只有一個一的二進位數
: 而該數x剛好會等於 word[i] 的狀態每個位數翻轉1，假定 word[i]=0000000010
: 0000000011 ^ 0000000010 = 0000000001
: 0000000000 ^ 0000000010 = 0000000010
: 0000000110 ^ 0000000010 = 0000000100
: 0000001010 ^ 0000000010 = 0000001000
: 0000010010 ^ 0000000010 = 0000010000
: 0000100010 ^ 0000000010 = 0000100000
: 0001000010 ^ 0000000010 = 0001000000
: 0010000010 ^ 0000000010 = 0010000000
: 0100000010 ^ 0000000010 = 0100000000
: 1000000010 ^ 0000000010 = 1000000000
: 所以我們去找前面所有 word[i] 翻轉一個位元的狀態共有幾個，全部累加起來就好。
: pycode:
: ---------------------------------------
: class Solution:
: def wonderfulSubstrings(self, word: str) -> int:
: cnt = [0] * 1024
: cnt[0] = 1
: mask = 0
: res = 0
: for c in word:
: # 更新狀態
: idx = ord(c) - ord('a')
: mask ^= (1 << idx)
: # 偶數
: res += cnt[mask]
: # 奇數
: for i in range(10):
: next = mask ^ (1 << i)
: res += cnt[next]
: cnt[mask] += 1
: return res
: ---------------------------------------
: 幹幹幹幹幹 這什麼死媽題目
: 這題他媽只有Medium你敢信==
思路:
差不多 我是有想到xor 但我沒想到那麼靠杯 最後看解答才懂
Python Code
class Solution:
def wonderfulSubstrings(self, word: str) -> int:
result = 0
count = [0]*1024
temp = 0
count[temp] = 1
for c in word:
temp ^= 1 << (ord(c) - ord('a'))
result += count[temp]
for i in range(10):
result += count[temp^(1<<i)]
count[temp] += 1
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.141.239 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714462592.A.629.html