821.字符的最短距离

链接：821.字符的最短距离
难度：Easy
标签：数组、双指针、字符串
简介：给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

题解 1 - cpp

• 编辑时间：2022-03-20
• 执行用时：4ms
• 内存消耗：6.7MB
• 编程语言：cpp
• 解法介绍：bfs。

class Solution {
   public:
    vector<int> shortestToChar(string s, char c) {
        unordered_set<string> sset;
        int n = s.size();
        vector<int> ans(n, -1);
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                q.push(i);
                ans[i] = 0;
            }
        }
        int level = 1, size = q.size();
        while (q.size()) {
            int idx = q.front();
            q.pop();
            if (idx < n - 1 && ans[idx + 1] == -1) {
                q.push(idx + 1);
                ans[idx + 1] = level;
            }
            if (idx > 0 && ans[idx - 1] == -1) {
                q.push(idx - 1);
                ans[idx - 1] = level;
            }
            if (--size == 0) {
                size = q.size();
                level++;
            }
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-04-19
• 执行用时：4ms
• 内存消耗：6.6MB
• 编程语言：cpp
• 解法介绍：bfs。

class Solution {
   public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        vector<int> check(n, -1);
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                q.push(make_pair(i, 0));
                check[i] = 0;
            }
        }
        while (q.size()) {
            pair<int, int> item = q.front();
            q.pop();
            int row = item.first, cnt = item.second;
            if (row < n - 1 && check[row + 1] == -1) {
                q.push(make_pair(row + 1, cnt + 1));
                check[row + 1] = cnt + 1;
            }
            if (row > 0 && check[row - 1] == -1) {
                q.push(make_pair(row - 1, cnt + 1));
                check[row - 1] = cnt + 1;
            }
        }
        return check;
    }
};