Leetcode: Shortest Distance to a Character

Shortest Distance to a Character



Similar Problems:


Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

  • S string length is in [1, 10000].
  • C is a single character, and guaranteed to be in string S.
  • All letters in S and C are lowercase.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution 1: BFS
// Blog link: https://code.dennyzhang.com/shortest-distance-to-a-character
// Basic Ideas: BFS
// Complexity: Time O(n), Space O(1)
func shortestToChar(S string, C byte) []int {
    res := make([]int, len(S))
    queue := []int{}
    for i, ch := range S {
        if byte(ch) == C {
            queue = append(queue, i)
            res[i] = 0
        } else {
            res[i] = -1
        }        
    }
    level := 0
    // BFS
    for len(queue) != 0 {
        level += 1
        len_queue := len(queue)
        for i:=0; i<len_queue; i++ {
            index := queue[0]
            queue = queue[1:]
            for _, offset := range []int{1, -1} {
                index2 := index+offset
                if index2>=0 && index2<=len(S)-1 && res[index2] == -1 {
                    queue = append(queue, index2)
                    res[index2] = level
                }
            }
        }
    }
    return res
}

  • Solution 2: Two pass. Update + Adjustment
// Blog link: https://code.dennyzhang.com/shortest-distance-to-a-character
// Basic Ideas: Two pass
//    Pass 1: left to right. Distance from previous C
//    Pass 2: right to left. Distance for min(old_distance, distance_from_following_C)
// Complexity: Time O(n), Space O(1)
func shortestToChar(S string, C byte) []int {
    res := make([]int, len(S))
    index := -len(S)
    for i, ch := range S {
        if ch == rune(C) { index = i }
        res[i] = i-index
    }

    index = 2*len(S)
    for i := len(S)-1; i>=0; i-- {
        ch := S[i]
        if ch == C { index = i}
        if index-i < res[i] { res[i] = index-i }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.