LeetCode 821. 字符的最短距离

821. 字符的最短距离

题目来源：821. 字符的最短距离

2022.04.19 每日一题

LeetCode 题解持续更新中GitHub仓库地址 CSDN博客地址

今天的题目就很简单 ，两次循环就可以了

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        // 获得字符串长度
        int n = s.size();
        // 开辟一个等长的数组
        vector<int> res(n);
        // 进行两次循环，每次更新数组下标对应的值
        // 找到最小值
        // 创建 index 变量记录 目标字符的 索引
        // 初始没有 记录为 -n 和 2*n
        // 定义这两个值是为了防止 字符串 s 中没有目标字符 c
        for (int i = 0, index = -n; i < n; i++) {
            if (s[i] == c) index = i;
            res[i] = i - index;
        }
        for (int i = n - 1, index = 2 * n; i >= 0; i--) {
            if (s[i] == c) index = i;
            res[i] = min(res[i], index - i);
        }
        return res;
    }
};

class Solution {
    public int[] shortestToChar(String s, char c) {
        // 获得字符串长度
        int n = s.length();
        // 开辟一个等长的数组
        int[] res = new int[n];
        // 进行两次循环，每次更新数组下标对应的值
        // 找到最小值
        // 创建 index 变量记录 目标字符的 索引
        // 初始没有 记录为 -n 和 2*n
        // 定义这两个值是为了防止 字符串 s 中没有目标字符 c
        for (int i = 0, index = -n; i < n; i++) {
            if (s.charAt(i) == c) index = i;
            res[i] = i - index;
        }
        for (int i = n - 1, index = 2 * n; i >= 0; i--) {
            if (s.charAt(i) == c) index = i;
            res[i] = Math.min(res[i], index - i);
        }
        return res;
    }
}

说句题外话，这道题目应该还可以整活，使用 BFS 算法来实现，晚上等我回宿舍了再来更新 BFS 的方法