前往
大廳
主題

LeetCode - 1876. Substrings of Size Three with Distinct Characters 解題心得

Not In My Back Yard | 2021-07-21 00:00:01 | 巴幣 0 | 人氣 120

題目連結:


題目意譯:
一個字串是「好」的,如果其不包含任何重複字元。

給定一字串 s ,回傳 s 中長度為 3 的好子字串之數量。

注意如果同樣的子字串出現多次,則每次的出現應獨立計算一次。

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

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



範例測資:
範例 1:
輸入: s = "xyzzaz"
輸出: 1
解釋: 有 4 個子字串長度為 3:"xyz" 、 "yzz" 、 "zza" 和 "zaz" 。
唯一一個好的長度為 3 之子字串為 "xyz" 。

範例 2:
輸入: s = "aababcabc"
輸出: 4
解釋: 有 7 個子字串長度為 3:"aab" 、 "aba" 、 "bab" 、 "abc" 、 "bca" 、 "cab" 和 "abc" 。
好的子字串為 "abc" 、 "bca" 、 "cab" 和 "abc" 。


解題思維:
窮舉即可所有長度為 3 的子字串即可(如這題窮舉長度 k 子陣列之方式),判斷每個子字串的三個字元是否皆相異(當然,如果 s 長度 ≦ 2 ,則不會有長度 3 的子字串)。如果是,則將 C + 1(C 作為計數器使用,一開始值為 0)。

最後的 C 值即為所求。




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

創作回應

更多創作