題目連結:
題目意譯:
你被給定一個索引值從 0 開始且只由小寫英文字母組成的字串 s,其中 s 中的每種字母恰好出現兩次。你同時也被給定一個索引值從 0 開始整數陣列 distance,其長度為 26。
字母表中每個字母編號依序為 0 到 25(即 'a' → 0 、 'b' → 1 、 'c' → 2 、……、 'z' → 25)。
在一個「適當間隔」字串中,第 i 種字母兩次出現中間夾著的字母數量恰好為 distance[i]。如果第 i 種字母沒有出現於 s 中,則 distance[i] 可以被忽略。
如果 s 為一個適當間隔的字串,則回傳真(True);反之,回傳假(False)。
限制:
2 ≦ s.length ≦ 52
s 只由小寫英文字母組成。
s 中每種字母恰好出現兩次。
distance.length == 26
0 ≦ distance[i] ≦ 50
範例測資:
範例 1:
輸入: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
輸出: true
解釋:
- 'a' 出現於索引值 0 和 2,所以滿足 distance[0] = 1。
- 'b' 出現於索引值 1 和 5,所以滿足 distance[1] = 3。
- 'c' 出現於索引值 3 和 4,所以滿足 distance[2] = 0。
注意到 distance[3] = 5,但由於 'd' 沒有出現於 s 中,因此它將被忽視。
因為 s 是一個適當間隔字串,所以回傳真。
範例 2:
輸入: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
輸出: false
解釋:
- 'a' 出現於索引值 0 和 1,所以兩者之間沒有夾著任何字母。
由於 distance[0] = 1,所以 s 不是一個適當間隔字串。
解題思維:
就單純地記錄每一種字母「前一次」出現的位置,然後對每一次「新出現」去計算兩者之間的索引值差,其值減 1 便可以得到中間夾了多少個字母。將該值與 distance 中對應的數字相比有無吻合即可。
如果每種字母每一次都符合,則 s 為一個適當間隔的字串;反之則不是。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。