Shortest Distance to a Character

Description

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:

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

Solution(javascript)

// /** 这题应该可以用 Stack
//  * @param {string} S
//  * @param {character} C
//  * @return {number[]}
//  */
// const shortestToChar = function (S, C) {
//   let stack = []
//   const result = new Array(S.length).fill(Infinity)
//   const handleIndex = (i) => {
//     if (S[i] === C) {
//       result[i] = 0
//       while (S[stack[stack.length - 1]] !== C && stack.length > 0) {
//         result[stack[stack.length - 1]] = Math.min(
//           result[stack[stack.length - 1]],
//           Math.abs(i - stack.pop()),
//         )
//       }
//     } else {
//       stack.push(i)
//     }
//   }
//   for (let i = 0; i < S.length; i++) {
//     handleIndex(i)
//   }
//   stack = []
//   for (let i = S.length - 1; i >= 0; i--) {
//     handleIndex(i)
//   }
//   return result
// }


/** 不用 Stack, 记录前一个 C 出现的位置
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
const shortestToChar = function (S, C) {
  const result = new Array(S.length).fill(Infinity)
  let prev = Infinity
  const handleIndex = (i) => {
    if (S[i] === C) {
      prev = i
    }
    result[i] = Math.min(
      result[i],
      Math.abs(i - prev),
    )
  }
  for (let i = 0; i < S.length; i++) {
    handleIndex(i)
  }
  prev = Infinity
  for (let i = S.length - 1; i >= 0; i--) {
    handleIndex(i)
  }
  return result
}