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
}