前往
大廳
主題

LeetCode - 1763. Longest Nice Substring 解題心得

Not In My Back Yard | 2021-06-23 00:00:01 | 巴幣 0 | 人氣 315

題目連結:


題目意譯:
一個字串 s 是很讚的,如果 s 包含的每個字母,其大寫以及小寫型態皆同時出現於其中。例如 "abABB" 很讚,因為 'A' 和 'a' 同時出現,而 'B' 和 'b' 也同時出現了。但是 "abA" 就不是了,因為 'b' 出現了,但是 'B' 卻沒有。

給定一字串 s ,回傳 s 中最長的、很讚的子字串。如果有多個存在,回傳最早出現的子字串。如果沒有任何存在,則回傳空字串。

限制:
1 ≦ s.length ≦ 100
s 由大寫以及小寫英文字母組成。



範例測資:
範例 1:
輸入: s = "YazaAay"
輸出: "aAa"
解釋: "aAa" 很讚因為 s 只包含字母表裡的 'A/a',而 'A' 和 'a' 同時出現了。
"aAa" 為很讚的最長子字串。

範例 2:
輸入: s = "Bb"
輸出: "Bb"
解釋: "Bb" 為一個很讚的字串因為 'B' 和 'b' 同時出現了。整個字串為一子字串。

範例 3:
輸入: s = "c"
輸出: ""
解釋: 沒有很讚的子字串存在。

範例 4:
輸入: s = "dDzeE"
輸出: "dD"
解釋: "dD" 和 "eE" 兩者都是很讚的最長子字串。
儘管有多個很讚的最長子字串,回傳 "dD" 因為其最早出現。


解題思維:
窮舉出所有子字串(藉由窮舉開頭以及結尾的位置,然後從長度最長的開始窮舉)並統計每個子字串的字母出現情況。

掃過字母的出現情況,當出現某個字母時其大寫以及小寫應同時存在於該子字串裡。如果沒有則代表該子字串不讚。如果有的話,因為我們是從長度最長的開始窮舉(為了找到最早出現的,相同長度的子字串我們也是從左到右窮舉出來),所以該子字串即為所求。

如果窮舉完之後,完全沒有找到任何很讚的子字串,即回傳空字串。




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

創作回應

更多創作