題目連結:
題目意譯:
給定一字串 S 以及一字元 C,回傳一個整數陣列代表著字串中每個字元離字元 C 的距離。
注:
字串 S 長度範圍 [1, 10000] 。
C 為單一字元,且保證一定會在 S 中。
S 所有字母以及 C 皆為小寫。
範例測資:
輸入: S = "loveleetcode" 、 C = 'e'
輸出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
解題思維:
先用一個陣列 P 將字元 C 在 S 中出現的位置全部記錄起來。
接著再掃過一次 S 中的所有字元,對於每個字元找到最近的兩個 C (如果有兩個的話),並計算該字元與這兩個 C 的位置值之差。這部分可以使用一個指標指到 P 目前最小的不超過該字元位置值去找到最近的兩個 C 或是直接使用二分搜尋法(Binary Search)去找。
接著將所有距離值存進一陣列之中回傳即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。