資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢母音出現次數均為偶數的最長子字串
假設我們有一個字串s（小寫），我們需要找到其中每個母音出現次數均為偶數的最長子字串的長度。
例如，如果輸入為s = "anewcoffeepot"，則輸出為10，因為子字串"wcoffeepot"包含兩個母音"o"和"e"，它們都出現了兩次。
為了解決這個問題，我們將遵循以下步驟：
vowels := 一個對映，將母音和數值關聯起來，例如{a:0, e:1, i:2, o:3, u:4}
prefix := 一個空對映，並在其中插入一個鍵值對(0, -1)
mask := 0, n := s的長度, res := 0
對於範圍從0到n的i，執行以下操作：
如果s[i]是母音，則
mask := mask XOR (2^vowels[s[i]])
如果prefix中不存在mask，則
prefix[mask] := i
否則，
res := res和(i - prefix[mask])中的最大值
返回res
讓我們來看下面的實現，以便更好地理解：
示例
class Solution:
def solve(self, s):
vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
prefix = {0: −1}
mask = 0
n = len(s)
res = 0
for i in range(n):
if s[i] in vowels:
mask ^= 1 << vowels[s[i]]
if mask not in prefix:
prefix[mask] = i
else:
res = max(res, i − prefix[mask])
return res
ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))輸入
"anewcoffeepot"
輸出
10
更新於: 2020年12月15日
355次瀏覽
廣告