主題

LeetCode - 821. Shortest Distance to a Character 解題心得

Not In My Back Yard | 2021-01-20 00:00:04

題目連結:


題目意譯:
給定一字串 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)去找。

接著將所有距離值存進一陣列之中回傳即是所求。




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

創作回應

更多創作