Leetcode Note: Go - Shortest Distance to a Character
Shortest Distance to a Character - LeetCode
https://leetcode.com/problems/shortest-distance-to-a-character/
- Go 言語で取り組んだメモ
所感
- string s, byte c が与えられる
- index i からの distance を int 配列で return する
回答
Shortest Distance to a Character - LeetCode
https://leetcode.com/problems/shortest-distance-to-a-character/solution/
Any language | Two pass | O(n), 0ms | Very easy with detailed explanation | Example on Golang - LeetCode Discuss
https://leetcode.com/problems/shortest-distance-to-a-character/discuss/1055141/Any-language-or-Two-pass-or-O(n)-0ms-or-Very-easy-with-detailed-explanation-or-Example-on-Golang
func shortestToChar(s string, c byte) []int {
// cache string length
var lens = len(s)
// prepare a storage for the result
// slice (or array, vector) with length equal to len(s) initialized with zeros
var res = make([]int, lens)
// current distance from last seen letter `c`
// we start with increadibly high value to show it's invalid
var dist = lens + 100
// scan from left to right, increase distance from last seen letter
// flush distance to zero at every new seen required letter
for i := 0; i < lens; i++ {
if s[i] == c {
dist = 0
}
res[i] = dist
dist++
}
// the same backwards
// but also check if we have less distance from opposite letter
for i := lens-1; i >=0; i-- {
if s[i] == c {
dist = 0
}
if dist < res[i] {
res[i] = dist
}
dist++
}
return res
}