题目地址(821. 字符的最短距离)

给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

示例 1:

输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
说明:

- 字符串 S 的长度范围为 [1, 10000]。
- C 是一个单字符，且保证是字符串 S 里的字符。
- S 和 C 中的所有字母均为小写字母。

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        ans = []

        for i in range(len(S)):
            # 从 i 向左向右扩展
            l = r = i
            # 向左找到第一个 C
            while l > -1:
                if S[l] == C: break
                l -= 1
            # 向左找到第一个 C
            while r < len(S):
                if S[r] == C: break
                r += 1
            # 如果至死没有找到，则赋值一个无限大的数字，由于题目的数据范围是 [1, 10000]，因此 -10000 或者  10000就够了。
            if l == -1: l = -10000
            if r == len(S): r = 10000
            # 选较近的即可
            ans.append(min(r - i, i - l))
        return ans

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        ans = [10000] * len(S)
        stack = []
        for i in range(len(S)):
            while stack and S[i] == C:
                ans[stack.pop()] = i - stack[-1]
            if S[i] != C:stack.append(i)
            else: ans[i] = 0
        for i in range(len(S) - 1, -1, -1):
            while stack and S[i] == C:
                ans[stack.pop()] = min(ans[stack[-1]], stack[-1] - i)
            if S[i] != C:stack.append(i)
            else: ans[i] = 0

        return ans

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        pre = -10000
        ans = []

        for i in range(len(S)):
            if S[i] == C: pre = i
            ans.append(i - pre)
        pre = 20000
        for i in range(len(S) - 1, -1, -1):
            if S[i] == C: pre = i
            ans[i] = min(ans[i], pre - i)
        return ans

class Solution {
    public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = -10000;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = i - prev;
        }

        prev = 20000;
        for (int i = N-1; i >= 0; --i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }
}

class Solution {
public:
   vector<int> shortestToChar(string S, char C) {
       vector<int> ans(S.size(), 0);
       int prev = -10000;
       for(int i = 0; i < S.size(); i ++){
           if(S[i] == C) prev = i;
           ans[i] = i - prev;
       }
       prev = 20000;
       for(int i = S.size() - 1; i >= 0; i --){
           if(S[i] == C) prev = i;
           ans[i] = min(ans[i], prev - i);
       }
       return ans;
   }
};

func shortestToChar(S string, C byte) []int {
    N := len(S)
    ans := make([]int, N)

    pre := -N // 最大距离
    for i := 0; i < N; i++ {
        if S[i] == C {
            pre = i
        }
        ans[i] = i - pre
    }

    pre = N*2 // 最大距离
    for i := N - 1; i >= 0; i-- {
        if S[i] == C {
            pre = i
        }
        ans[i] = min(ans[i], pre-i)
    }
    return ans
}

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

class Solution
{

    /**
     * @param String $S
     * @param String $C
     * @return Integer[]
     */
    function shortestToChar($S, $C)
    {
        $N = strlen($S);
        $ans = [];

        $pre = -$N;
        for ($i = 0; $i < $N; $i++) {
            if ($S[$i] == $C) {
                $pre = $i;
            }
            $ans[$i] = $i - $pre;
        }

        $pre = $N * 2;
        for ($i = $N - 1; $i >= 0; $i--) {
            if ($S[$i] == $C) {
                $pre = $i;
            }
            $ans[$i] = min($ans[$i], $pre - $i);
        }
        return $ans;
    }
}