Link to LeetCode Problem

S1: 中心扩展法

这是最符合直觉的思路，对每个字符分别进行如下处理：

• 从当前下标出发，分别向左、右两个方向去寻找目标字符 C。
• 只在一个方向找到的话，直接计算字符距离。
• 两个方向都找到的话，取两个距离的最小值。

https://camo.githubusercontent.com/efaa1cd00bcef4ff7e2cf0c5cd7a37a60d403cf9f82439dffb63a1a48dcf3e06/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f3832315f302e706e67

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> res(S.length());

        for (int i = 0; i < S.length(); i++) {
            if (S[i] == C) continue;

            int left = i;
            int right = i;
            int dist = 0;

            while (left >= 0 || right <= S.length() - 1) {
                if (S[left] == C) {
                    dist = i - left;
                    break;
                }
                if (S[right] == C) {
                    dist = right - i;
                    break;
                }

                if (left > 0) left--;
                if (right < S.length() - 1) right++;
            }

            res[i] = dist;
        }

        return res;
    }
}

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  // 结果数组 res
  var res = Array(S.length).fill(0);

  for (let i = 0; i < S.length; i++) {
    // 如果当前是目标字符，就什么都不用做
    if (S[i] === C) continue;

    // 定义两个指针 l, r 分别向左、右两个方向寻找目标字符 C，取最短距离
    let l = i,
      r = i,
      shortest = Infinity;

    while (l >= 0) {
      if (S[l] === C) {
        shortest = Math.min(shortest, i - l);
        break;
      }
      l--;
    }

    while (r < S.length) {
      if (S[r] === C) {
        shortest = Math.min(shortest, r - i);
        break;
      }
      r++;
    }

    res[i] = shortest;
  }
  return res;
};

• Time: $O(N^2)$，N 为 S 的长度，两层循环。
• Space: $O(1)$

S2: 空间换时间

空间换时间是编程中很常见的一种 trade-off (反过来，时间换空间也是)。

• 因为目标字符 C 在 S 中的位置是不变的，所以我们可以提前将 C 的所有下标记录在一个数组 cIndices 中。
• 然后遍历字符串 S 中的每个字符，到 cIndices 中找到距离当前位置最近的下标，计算距离。

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();
        vector<int> c_indices;
        // Initialize a vector of size n with default value n.
        vector<int> res(n, n);

        for (int i = 0; i < n; i++) {
            if (S[i] == C) c_indices.push_back(i);
        }

        for (int i = 0; i < n; i++) {
            if (S[i] == C) {
                res[i] = 0;
                continue;
            }

            for (int j = 0; j < c_indices.size(); j++) {
                int dist = abs(c_indices[j] - i);
                if (dist > res[i]) break;
                res[i] = dist;
            }
        }

        return res;
    }
};

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  // 记录 C 字符在 S 字符串中出现的所有下标
  var cIndices = [];
  for (let i = 0; i < S.length; i++) {
    if (S[i] === C) cIndices.push(i);
  }

  // 结果数组 res
  var res = Array(S.length).fill(Infinity);

  for (let i = 0; i < S.length; i++) {
    // 目标字符，距离是 0
    if (S[i] === C) {
      res[i] = 0;
      continue;
    }

    // 非目标字符，到下标数组中找最近的下标
    for (const cIndex of cIndices) {
      const dist = Math.abs(cIndex - i);

      // 小小剪枝一下
      // 注：因为 cIndices 中的下标是递增的，后面的 dist 也会越来越大，可以排除
      if (dist >= res[i]) break;

      res[i] = dist;
    }
  }
  return res;
};

• Time: $O(N*K)$，N 是 S 的长度，K 是字符 C 在字符串中出现的次数，K <= N。