我對一類常考算法面試題的詳細(xì)分析

給你一個(gè)字符串 s ，請你返回滿足以下條件的最長子字符串的長度：每個(gè)元音字母，即?'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出現(xiàn)了偶數(shù)次。

示例 1：

輸入：s =?"leetminicoworoep"
輸出：13
解釋：最長子字符串是?"leetminicowor"?，它包含 e，i，o 各 2 個(gè)，以及?0?個(gè) a，u 。

示例 2：

輸入：s =?"leetcodeisgreat"
輸出：5
解釋：最長子字符串是?"leetc"?，其中包含 2 個(gè) e 。

示例 3：

輸入：s =?"bcbcbc"
輸出：6
解釋：這個(gè)示例中，字符串?"bcbcbc"?本身就是最長的，因?yàn)樗械脑?a，e，i，o，u 都出現(xiàn)了?0?次。

提示：

1?<=?s.length?<=?5?x?10^5
s 只包含小寫英文字母。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts

2 分析過程

創(chuàng)建一個(gè)狀態(tài)機(jī)：

• 對于非元音字符放置到位置0處，
• 元音字符'a'放置到位置1處，
• 元音字符'e'放置到位置2處，
• 元音字符'i'放置到位置4處，
• 元音字符'o'放置到位置8處，
• 元音字符'u'放置到位置16處

元音字符之所以放到1，2，4，8，16，是要為位運(yùn)算創(chuàng)造條件，二進(jìn)制表示中這些數(shù)字都只有1位為1，其他位置都為0. 很明顯，為1的位置是標(biāo)志位。

以處理leetcode字符串為例：

狀態(tài)機(jī)有如下6個(gè)取值，非元音字符放置到0處：

處理第二個(gè)字符e時(shí)，放置到2處：

第三個(gè)字符又是e，再次放置到2處：

下面又是兩個(gè)非元音字符，到字符c為止，字符串leetc就是滿足題意(單個(gè)元音字符出現(xiàn)偶數(shù)次)的最大子字符串。

判斷元音字符出現(xiàn)偶數(shù)次的方法：二進(jìn)制表示下，且6個(gè)值(0,1,2,4,8,16)都只有一個(gè)位為1，所以使用異或運(yùn)算，某個(gè)元音字符出現(xiàn)偶數(shù)次時(shí)，此位最終狀態(tài)必然為0；奇數(shù)次時(shí)最終值必然為1.

接下來，處理下一個(gè)字符o，但是后面沒有字符o，只出現(xiàn)1次，不滿足題意：

接下來一樣方法處理剩余字符，所以整個(gè)字符串滿足題意的最長子串為：leetc

如果字符串修改為：leetcodoe，滿足題意的最長子串：leetcodo.

3 代碼

基于以上分析，再看下面代碼就不難理解：

class?Solution(object):
????def?findTheLongestSubstring(self,s):
????????state,?statedict?=??0,?{0:-1}?#設(shè)置此初始值決定下面的代碼?i-statedict[state]?這樣寫
????????maxlen?=?0
????????codedict?=?{'a':1,'e':2,'i':4,'o':8,'u':16}
????????for?i,c?in?enumerate(s):
????????????if?c?in?codedict:
????????????????state?^=?codedict[c]
????????????if?state?in?statedict:
????????????????maxlen?=?max(maxlen,i-statedict[state])
????????????else:
????????????????statedict[state]?=?i?#?記憶新的狀態(tài)值，二進(jìn)制位下，可能會出現(xiàn)類似"第1位或第3位為1"的32種組合
????????return?maxlen

statedict 設(shè)置{0:-1}初始值，也是很有講究、很巧妙的，決定了下面的代碼 i-statedict[state] 這樣寫

statedict[state] = i 記憶新的狀態(tài)值，二進(jìn)制位下，可能會出現(xiàn)類似第1位或第3位為1的32種組合。

4 擴(kuò)展

今天題目與Day50的思路極為類似，Day50: 連續(xù)數(shù)組，可以歸納為前綴和問題。

此類問題關(guān)鍵是想辦法巧妙的處理各種狀態(tài)，區(qū)分各種狀態(tài)。記憶某種狀態(tài)，中間經(jīng)歷某種變換或抵消操作后，出現(xiàn)了狀態(tài)字典里的某個(gè)狀態(tài)，表明找到滿足題意的前綴。

比如，字符串lee，第一個(gè)狀態(tài)是l，第二個(gè)是le，第三個(gè)狀態(tài)又是l，因?yàn)?個(gè)e能抵消。因此，滿足題意的最長子串長度為3.

字符串oeo，第一個(gè)狀態(tài)是o，第二個(gè)狀態(tài)oe，第三個(gè)狀態(tài)是e，兩個(gè)o抵消，因此沒有重復(fù)狀態(tài)。因此，滿足題意的最長子串長度為0.