前往
大廳
主題

LeetCode - 1839. Longest Substring Of All Vowels in Order 解題心得

Not In My Back Yard | 2024-02-10 12:00:21 | 巴幣 0 | 人氣 48

題目連結:


題目意譯:
一個字串如果其滿足以下條件,則其被視為美麗的:
    5 個英文母音('a' 、 'e' 、 'i' 、 'o' 、 'u')每一個都應出現至少一次、
    所有字母應按字典序排序(即所有 'a' 出現於 'e' 前,所有 'e' 出現於 'i' 前等等)。

例如,字串 "aeiou" 和 "aaaaaaeiiiioou" 是美麗的,但是 "uaeio" 、 "aeoiu" 和 "aaaeeeooo" 則是不美麗的。

給定一個字串 word,其只由英文母音所組成。回傳 word 中的最長美麗子字串的長度。如果不存在這樣子的子字串,則回傳 0。

一個子字串為一個字串中的連續字元序列。

限制:
1 ≦ word.length ≦ 5 × 10 ^ 5
word 由字元 'a' 、 'e' 、 'i' 、 'o' 和 'u'。



範例測資:
範例 1:
輸入: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
輸出: 13
解釋: word 中的最長美麗子字串為 "aaaaeiiiiouuu",其長度 13。

範例 2:
輸入: word = "aeeeiiiioooauuuaeiou"
輸出: 5
解釋: word 中的最長美麗子字串為 "aeiou",其長度 5。

範例 3:
輸入: word = "a"
輸出: 0
解釋: 沒有美麗子字串存在,所以回傳 0。


解題思維:
就是單純地從掃過一次 word 並從 'a' 到 'e' 配對即可。

也就是說一開始我們想找 'a',所以會先找到第一個 'a',接著我們會把接下來的連續 'a' 全部掃過一次;接著到這一批 'a' 結束後,我們想要配對 'e'。因此如果現在看到的字元不是 'e',則跳回到 'a' 開始配對。如果是 'e',則重複類似 'a' 的動作……以此類推。

而我們每一次配對 'u',便看現在已配對完成的子字串長度是否大過最大值。如果是就將該值更新為現在的長度。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作