0821. Shortest Distance to a Character (E)

题目

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the shortest distance from s[i] to the character c in s.

Example 1:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Example 2:

Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:

• 1 <= s.length <= 10^4
• s[i] and c are lowercase English letters.
• c occurs at least once in s.

题意

根据字符串s生成数组arr，arr[i]表示s中下标为i的字符到距离它最近的字符c的距离。

思路

维护两个数组left和right。left[i]表示下标i的元素到它左边最近的c的距离，right[i]表示下标i的元素到它右边最近的c的距离，最后比较left[i]和right[i]即可。

代码实现

Java

class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] left = new int[s.length()], right = new int[s.length()];
        int dl = -1, dr = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                dl = 0;
            } else {
                left[i] = dl == -1 ? Integer.MAX_VALUE : ++dl;
            }
            int j = s.length() - 1 - i;
            if (s.charAt(j) == c) {
                dr = 0;
            } else {
                right[j] = dr == -1 ? Integer.MAX_VALUE : ++dr;
            }
        }
        int[] ans = new int[s.length()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = Math.min(left[i], right[i]);
        }
        return ans;
    }
}