821. Shortest Distance to a Character #

Problem #

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the shortest distance from s[i] to the character c in s.

Example 1:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Example 2:

Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:

1 <= s.length <= 104
s[i] and c are lowercase English letters.
c occurs at least once in s.

Problem Summary #

Given a string S and a character C. Return an array representing the shortest distance from each character in string S to the character C in string S.

Solution Ideas #

Solution 1: Update the distance to C once from left to right, then update it once from right to left, and take the minimum of the two.
Solution 2: Scan string S sequentially. For each character that is not C, scan left once and right once respectively, calculate the distance to the target character C, then take the minimum of the left and right distances and store it in the final answer array.

Code #


package leetcode

import (
	"math"
)

// Solution 1
func shortestToChar(s string, c byte) []int {
	n := len(s)
	res := make([]int, n)
	for i := range res {
		res[i] = n
	}
	for i := 0; i < n; i++ {
		if s[i] == c {
			res[i] = 0
		} else if i > 0 {
			res[i] = res[i-1] + 1
		}
	}
	for i := n - 1; i >= 0; i-- {
		if i < n-1 && res[i+1]+1 < res[i] {
			res[i] = res[i+1] + 1
		}
	}
	return res
}

// Solution 2
func shortestToChar1(s string, c byte) []int {
	res := make([]int, len(s))
	for i := 0; i < len(s); i++ {
		if s[i] == c {
			res[i] = 0
		} else {
			left, right := math.MaxInt32, math.MaxInt32
			for j := i + 1; j < len(s); j++ {
				if s[j] == c {
					right = j - i
					break
				}
			}
			for k := i - 1; k >= 0; k-- {
				if s[k] == c {
					left = i - k
					break
				}
			}
			res[i] = min(left, right)
		}
	}
	return res
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}