【Day 2 】2021-09-11 - 821. 字符的最短距离

[azl397985856]

821. 字符的最短距离

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/shortest-distance-to-a-character

前置知识

• 数组的遍历(正向遍历和反向遍历)

  题目描述

  
  给定一个字符串 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 中的所有字母均为小写字母。

[BreezePython]

思路

1. 既然我们需要找到最短距离，那么首先应该获取到该字符在字符串 s 中的所有下标位置。
2. 使用O(n)的时间遍历一次字符串，并将等于目标字符的下标添加至动态数组arr中。
3. 初始化指针p，指向arr的0位置
4. 创建 ret 数组，长度为len(s)
5. 再次遍历s的过程中，我们需要判断当满足以下两点条件时，指针 p 右移一位
   1. p小于arr最大下标
   2. 前下标i 到 p + 1的绝对距离比到 p 的绝对距离小
6. 每次将 p - i 的绝对距离添加至 ret[i] 中
7. 最终返回ret即可

代码

Python:

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        ret, p, arr = [], 0, [i for i in range(len(s)) if s[i] == c]
        for i, j in enumerate(s):
            if p < len(arr) - 1 and abs(arr[p] - i) > abs(arr[p + 1] - i):
                p += 1
            ret.append(abs(arr[p] - i))
        return ret

Java:

class Solution {
    public int[] shortestToChar(String s, char c) {
        ArrayList<Integer> arr = new ArrayList<>();
        int[] ret = new int[s.length()];
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) arr.add(i);
        }
        for (int i = 0; i < s.length(); i++) {
            if (p < arr.size() - 1 && Math.abs(arr.get(p) - i) > Math.abs(arr.get(p + 1) - i)) p++;
            ret[i] = Math.abs(arr.get(p) - i);
        }
        return ret;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[yachtcoder]

两次遍历 左到右然后右到左

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:

        ans = [0]*len(s)
        lastc = float('inf')
        for i, ch in enumerate(s):
            if ch == c:
                ans[i] = 0
                lastc = i
            else:
                ans[i] = abs(lastc - i)
        for i in range(len(s)-1, -1, -1):
            ch = s[i]
            if ch == c:
                ans[i] = 0
                lastc = i
            else:
                ans[i] = min(ans[i], abs(lastc - i))
        return ans

Time: O(n) Space: Constant with O(n) for answer

[leungogogo]

LC821. Shortest Distance to a Character

Main Idea

One Scan with Two Pointers

We use prev array to record the previous appearance of c and next array to record the next for each character in the string.

For the first character, initialize its prev[0] to be infinity. Then for each character s[i], if s[i] == c, then prev[i] = 0, else, prev[i] = prev[i - 1] + 1, notice if prev[i - 1] == Integer.MAX_VALUE, we don't need to add 1 so it won't cause integer overflow.

Similar logic for next array.

Then for each character, res[i] = min{prev[i], next[i]}.

Also we can use two pointers to acheive our goal with one scan.

Code

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] next = new int[n], prev = new int[n], res = new int[n];
        for (int i = 0; i < n; ++i) {
            int j = n - 1 - i;
            if (i == 0) {
                prev[i] = s.charAt(i) == c ? 0 : Integer.MAX_VALUE;
                next[j] = s.charAt(j) == c ? 0 : Integer.MAX_VALUE;
            } else {
                prev[i] = s.charAt(i) == c ? 0 : prev[i - 1] == Integer.MAX_VALUE ? prev[i - 1] : prev[i - 1] + 1;
                next[j] = s.charAt(j) == c ? 0 : next[j + 1] == Integer.MAX_VALUE ? next[j + 1] : next[j + 1] + 1;

                if (i >= j) {
                    res[i] = Math.min(prev[i], next[i]);
                    res[j] = Math.min(prev[j], next[j]);
                }
            }
        }
        return res;
    }
}

Complexity Analysis

Time: O(n) Space: O(n)

[ImSingee]

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

func shortestToChar(s string, c byte) []int {
    result := make([]int, len(s))

    left := -20000
    for i := 0; i < len(s); i++ {
        cc := s[i]

        if cc == c {
            left = i
        }

        result[i] = i - left
    }

    right := 20000
    for i := len(s) - 1; i >= 0; i-- {
        cc := s[i]

        if cc == c {
            right = i
        }

        result[i] = min(right - i, result[i])
    }

    return result
}

时间复杂度 O(len(s)) 额外空间复杂度 O(1)

[q815101630]

Thought

Traverse the array twice, one time we traverse from left to right, the second time we traverse from the back. In the first iteration, we record a temporary variable for the index where s[i] == c, then we can know all the distance of a character with a c character behind it. Then in the opposite direction, we determine if a c on the left side or on the right side is the closest for it.

python

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        N = len(s)
        ans = [100000] * N
        closeLoc = -100000
        for i in range(N):
            if s[i] == c:
                closeLoc = i
                ans[i] = 0
            else:
                ans[i] = min(i-closeLoc, ans[i])

        closeLoc = 100000
        for i in range(N-1, -1, -1):
            if s[i] == c:
                closeLoc = i
            else:
                ans[i] = min(closeLoc-i, ans[i])

        return and

Time Complexity: O(n) Space Complexity: O(n)

[yanglr]

思路

题意: 计算 abs[i] = indexGap(i, 最近的字符c), 1 <= s.length <= 10^4 输出 abs[i]的数组

解法: 双指针 中心扩展

使用一个结果数组 gaps[]

将string s转为字符数组，然后从前往后遍历。 循环变量记作i, 对于每一趟: 如果当前字符就是要搜索的字符c, 距离记为 0，否则分别向左、向右找最近的字符c。 向左找, 找到第一个字符c, 将指针i与之的index之差记作leftDistance。 向右找, 找到第一个字符c, 将指针i与之的index之差记作rightDistance。 取两者的较小值。

依次填充 gaps[i] 的值即可。

代码

实现语言: C++

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> gaps(s.size());
        vector<char> chars(s.begin(), s.end());

        for (int i = 0; i < chars.size(); i++)
        {
            // 如果当前字符就是要搜索的字符c, 距离为 0
            if (chars[i] == c) gaps[i] = 0;
            else /* 否则分别向左、向右找最近的字符c */
            {
                int leftDistance = INT_MAX, rightDistance = INT_MAX;
                for (int left = i; left >= 0; left--)
                {
                    if (chars[left] == c) // 向左找, 找到第一个
                    {
                        leftDistance = i - left;
                        break;
                    }
                }
                for (int right = i; right < chars.size(); right++) // 向右找, 找到第一个
                {
                    if (chars[right] == c)
                    {
                        rightDistance = right - i;
                        break;
                    }
                }
                gaps[i] = min(leftDistance, rightDistance);
            }
        }

        return gaps;
    }
};

代码已同步上传到: leetcode-ac/91algo - github.com

复杂度分析

• 时间复杂度：O(n^2)，其中 n 为字符串长度。
• 空间复杂度：O(n)

[BpointA]

思路

分别遍历两次数组。 第一次从右向左遍历，记录s每个字母与最近的c的距离。第二次从左向右遍历，同步将距离更新为左右中较小的距离。

python3代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        res=[len(s)]*len(s)
        temp=len(s)
        for i in range(len(s)-1,-1,-1):
            if s[i]!=c and temp==len(s):
                continue
            elif s[i]==c:
                temp=i
                res[i]=0
            else:
                res[i]=temp-i
        temp=-1
        for i in range(len(s)):
            if s[i]!=c and temp==-1:
                continue
            elif s[i]==c:
                temp=i
                res[i]=0
            else:
                res[i]=min(res[i],i-temp)
        return res                              

复杂度分析

时间复杂度：O(n) 其中n为数组长度，具体时间复杂度为O(2n) 空间复杂度：O(n)

[ZiyangZ]

• Time and space O(n).

class Solution {
    public int[] shortestToChar(String s, char c) {
        List<Integer> index = new ArrayList<>();
        index.add(Integer.MAX_VALUE);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) index.add(i);
        }
        index.add(Integer.MAX_VALUE);

        int[] ans = new int[s.length()];
        int i = 1;
        for (int j = 0; j < s.length(); j++) {
            ans[j] = Math.min(Math.abs(j - index.get(i)), Math.abs(j - index.get(i - 1)));
            if (j == index.get(i)) i++;
        }

        return ans;
    }
}

[fzzfgbw]

思路

从左遍历，找到左边最近距离； 从右边遍历，找到右边最近的距离并与之前左边最近距离相比较。

代码

func shortestToChar(s string, c byte) []int {
    var ans []int
    curr := -len(s)
    for i := range s {
        if s[i] == c {
            curr = i
            ans = append(ans, 0)
        } else {
            ans = append(ans, i-curr)
        }
    }
    curr = 2*len(s)
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] != c {
            if curr-i < ans[i] {
                ans[i] = curr - i
            }
        } else {
            curr = i
        }
    }
    return ans
}

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(1)。

[mosihan]

题目

821字符的最短距离

思路

正则化匹配符合要求的index，对原数组的每个索引与匹配好的数组索引做差，取绝对值后的min即为该索引到目标字符的最小距离

code

import re
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        f=re.finditer(c[0],s)

        s_index=[]
        for i in f:
            s_index.append(i.span()[0])
        print(s_index)

        index1=range(len(s))
        index2=[]
        dis_min=float("inf")
        for j in index1:
            for k in s_index:
                dis_min=min(dis_min,abs(k-j))
            index2.append(dis_min)
            dis_min=float("inf")

        return index2

复杂度

• 时间复杂度

  O(m*n)

• 空间复杂度

  O(m*n)

[a244629128]

思路

两次遍历，第一次从左到右把最近距离更新到res array 第二次 从右到左遍历，然后把第二次得到的最短距离和第一次相比取最小值 更新 res array

var shortestToChar = function(s, c) {
    //两个循环，设prev 为 INFINITY
    //第一个循环从左到右，每次在s找到 c 这个字符 就更新 prev = i（c 这个字符的INDEX）
    // 然后让最近更新的 c 字符 Index 和 当前 字符 INDEX 相减 取绝对值（因为从左到右，不取绝对值会得到负数）
    let prev = Infinity;
    let res = [];
    for(let i =0; i<s.length;i++){
        if(s[i] === c){
            prev = i;
        }
        res[i] = Math.abs(prev-i);
    }
    //第一次循环之后 res 里面的结果，当前数值还没完全正确
// I I I 0 1 0 0 1 2 3 4  ，I = Infinity

    // reset prev to INFINITY
    prev = Infinity;
    // 第二次循环从右到左， 跟第一次循环步骤一样
    for(let j = s.length-1; j>=0; j--){
        if(s[j] === c){
            prev = j;
        }
        // 不同的地方是这里 对比第一次循环和第二次循环得到的值，然后取最小值更新res
        res[j] = Math.min(res[j],prev-j);
    }
    return res;
};

//time O(n)
// space O(n)

[leo173701]

思路：维护一个滑动窗口[left, right]，不断调整窗口的位置 left=right right = new location

1. 第一遍遍历, 统计所在的位置temp
2. 如果temp只有一个元素， 那就直接再遍历一次，直接返回结果res
3. 如果temp 有2个及其以上元素，那就用滑动窗口 时间复杂度： O(n) 空间复杂度： O(n)

` Python3 : def shortestToChar(self, s: str, c: str) -> List[int]:

    temp = []
    for i in range(len(s)):
        if c==s[i]:
             temp.append(i)
    res = [-1 for _ in range(len(s))]
    # print(temp)
    if len(temp)==1:
        res = [abs(i-temp[0]) for i in range(len(s))]
        return res
    left = temp[0]
    right = temp[1]
    j=1
    for i in range(len(s)):
        if i<=temp[0]:
            res[i] = temp[0]-i
            continue
        elif i>=temp[-1]:
            res[i]=i-temp[-1]
        elif i==left:
                res[i]=0
        elif i==right:
            res[i]=0
            if j<(len(temp)-1):
                left = right
                j+=1
                right = temp[j]
                # print("now it's time to shift window, new left=",left," right=",right)
        else:
            res[i] = min(abs(i-left), abs(right-i))
            # print("i is inside the window")
            # print("     i = ",i,",res[i]=",res[i])
            # print("          left = ",left)
            # print("          right = ",right)
    return res`

[chang-you]

思路

我们要找到左右最短距离，所以从左右两边都要分别遍历一遍，比较更新取二者较小值。

关键点

pos初始值的initialize。
由于我们要取最小值，所以要取一个较大数的初始值，
因为res[i] = i - pos，所以pos如果initialize为Integer MIN_VALUE, i-Integer MIN_VALUE会越界。
如果取Integer MAX_VALUE，最小值始终会是这个。
所以我们取数组长度的最大值稍大的即可，即-s.length();

代码

Java

// Time = O(n)
// Space = O(n)
class Solution {
    public int[] shortestToChar(String S, char C) {
        int n = S.length();
        int[] res = new int[n];
        int pos = -n;

        for (int i = 0; i < n; i++) {
            if (S.charAt(i) == C) {
                pos = i;
            }
            res[i] = i - pos;
        }

        for (int i = n - 1; i >= 0; i--) {
            if (S.charAt(i) == C) {
                pos = i;
            }
            res[i] = Math.min(res[i], Math.abs(i - pos));
        }

        return res;

    }
}

复杂度

Time=O(n) 左右两个for loop

Space=O(n) 开辟String长度的数组。

[ai2095]

LC 821 Shortest Distance to a Character

https://leetcode.com/problems/shortest-distance-to-a-character/

Topics

• Array
• String

Similar Questions

Hard

• https://leetcode.com/problems/shortest-common-supersequence/

Medium

• https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/
• https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

Easy

思路

1. Find all c ocurrences and save them into one list.
2. Update the corresponding position in res to 0
3. Update other elements in the result list

代码 Python

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        # Helper function to update other elements.
        def update_res(index):
            # Update the lower part
            i = index
            while i > 0 and res[i] + 1 < res[i-1]:
                res[i-1] = res[i] + 1
                i -= 1
            j = index
            while j < len(res) - 1 and res[j] + 1 < res[j+1]:
                res[j+1] = res[j] + 1
                j +=1

        res = [float("inf")]*len(s)
        # Find all c ocurrences and save them into one list.
        # Update the corresponding position in res to 0
        c_l = []
        for i, e in enumerate(s):
            if e == c:
                c_l.append(i)
                res[i] = 0

        # Update other elements in the result list
        for idx in c_l:
            update_res(idx)

        return res

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N) N is the # of occurrence of c in s.

[st2yang]

思路

• 数组正反向遍历

代码

• python

  class Solution:
  def shortestToChar(self, s: str, c: str) -> List[int]:
      n = len(s)
      res = [inf] * n
  
      l = -inf
      for i in range(n):
          if s[i] == c:
              l = i
          res[i] = i - l
  
      r = inf
      for i in range(n - 1, -1, -1):
          if s[i] == c:
              r = i
          res[i] = min(r - i, res[i])
  
      return res

复杂度

• 时间: O(n)
• 空间: O(1)

[cicihou]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        c_position = [i for i in range(len(s)) if s[i] == c]
        return [min([abs(c-i) for c in c_position]) for i in range(len(s))]

time: O(len(s) * len(c)) space: O(len(c))

[qixuan-code]

821. Shortest Distance to a Character

comment Runtime: 146 ms beat 5%

python代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        temp = []
        res = []
        for i in range(len(s)):
            if s[i] == c:
                temp.append(i)

        for j in range(len(s)):
            a = [abs(x-j) for x in temp]
            res.append(min(a))

        return res

复杂度分析

• 时间复杂度：O(N^2+N)
• 空间复杂度：O(N)

[MonkofEast]

821. Shortest Distance to a Character

Click Me

Algo

0. Greedy
1. Loop from lft, find the dis to cloest 'c' on the lft Should init a float('-inf') for first non 'c's
2. Loop from lft, fint the dis to cloest 'c' on the rgt Should init a float('-inf') for first non 'c's
3. Save the min() from 1 & 2 Can be integrated into stp-2

Code

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        # greedy
        # init a res list 
        res = []

        # save previous loc of 'c', use '-inf' for the first non 'c's
        prev = float('-inf') # S: O(1)

        # start from left, cal the distance of cloest 'c' on the left, record
        for i in range(len(s)):
            if s[i] == c:
                prev = i
                res.append(0)
                continue
            res.append(i - prev)

        # reset prev for the first non 'c's
        prev = float('inf')

        # start from right, cal the distanc of cloest 'c' on the right, record
        for i in range(len(s) - 1, -1, -1):
            if s[i] == c:
                prev = i
                continue
            res[i] = min(res[i], prev - i)
        return res

Comp

T: O(N)

S: O(1)

[mmboxmm]

思路

Scan the string twice, from left and from right. Update the min.

代码

fun shortestToChar(s: String, c: Char): IntArray {
  val res = IntArray(s.length) { s.length }
  var last = -1
  for ((index, ch) in s.withIndex()) {
    if (ch == c) {
      last = index
      res[index] = 0
    } else if (last != -1) {
      res[index] = index - last
    }
  }

  last = -1
  for (index in res.size - 1 downTo 0) {
    if (res[index] == 0) {
      last = index
    } else if (last != -1) {
      res[index] = minOf(res[index], last - index)
    }
  }
  return res
}

复杂度

• Time: O(n)
• Space: O(1), no extra space.

[ruohai0925]

思路

关键点

• 正反遍历

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        n = len(S)
        dis = 10001
        res = []
        for i in range(0, n):
            if S[i] == C:
                dis = 0
            res.append(dis)
            dis += 1

        dis = 10001
        for i in range(n - 1, -1, -1):
            if S[i] == C:
                dis = 0
            res[i] = min(res[i], dis)
            dis += 1
        return res

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[kidexp]

Thoughts

assume s length is n

take S = "loveleetcode", C = 'e' as an example

first we compute the position of C in S, we can get T [3,5,6,11], O(n), if S only contains chars of C then T will have same length as S.

then we can use one pointer (c_index) to indicate which position of C in S we are referring to we iterate through S with index i, each time we will only compare at the position of current char in S with two positions in T, (c_index, and c_index+1), and chose the minimal difference Whenever s[I] is equal to next position in T, we will update c_index

the whole two pointers approach takes at most 2n which is O(n)

code

from typing import List

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        positions = [i for i in range(len(s)) if s[i] == c]
        c_index = 0
        results = []
        for i in range(len(s)):
            if c_index < len(positions) - 1 and i == positions[c_index + 1]:
                c_index += 1
            if c_index == len(positions) - 1:
                results.append(abs(i - positions[c_index]))
            else:
                results.append(
                    min(abs(i - positions[c_index]), abs(positions[c_index + 1] - i))
                )
        return results

Complexity

Time complexity: O(n)

Space Complexity: O(n)

[falconruo]

思路:

。从左到右依次遍历字符串S，比较每个字符与字符C的最短距离并存放到返回数组res中 。从右到左依次遍历字符串S，比较每个字符与字符C的最短距离并与之前存放在数组res中的距离取小值

复杂度分析:

时间复杂度: O(n), n为字符串s的长度 空间复杂度: O(1)

代码(C++):

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.length();
        vector<int> res(n, n - 1);

        int idx = n - 1;
        for (int i = 0; i < n; ++i) {
            if (s[i] == c)
                idx = i;
            res[i] = min(res[i], abs(idx - i));
        }

        idx = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == c)
                idx = i;
            res[i] = min(res[i], abs(idx - i));
        }

        return res;
    }
};

[JiangyanLiNEU]

Two ideas

Straightforward way (Runtime = O(n), Space = O(n))

• I get all the index of letter c in s
• CASE1, any letter before the first c letter, the distance will be (c_index - letter_index)
• CASE2, any letter in between two c letters, we need to find the middle point. The distance will be (letter_index-c_index) and then after middle point, it will be (c_index-letter_index)
• CASE3, any letter after the last c letter, the distance will be (letter_index - last_c_index)

forward and backward update (Runtime = O(n), Space = O(n))

• Iterate from left to right, the distance is always the distance to the right nearest letter c
• Iterate from right to left, update the distance to be the minimum distance of current one and distance to the left nearest letter c

Implement straightforward idea

class Solution(object):
    def shortestToChar(self, s, c):
        # get all the location of letter c
        c_location = [i for i in range(len(s)) if s[i]==c
        result = []
        #case 1
        for i in range(c_location[0]+1):
            result.append(c_location[0]-i)
        #case 2
        while len(c_location) >= 2:
            popStart = c_location.pop(0)
            endAt = c_location[0]
            index = popStart + 1
            while index <= (endAt+popStart)//2:
                result.append(index-popStart)
                index += 1
            while index <= endAt:
                result.append(endAt-index)
                index+=1 
        #case 3
        for i in range(c_location[0]+1,len(s)):
            result.append(i-c_location[0])
        return result

Implement smarter idea

class Solution(object):
    def shortestToChar(self, s, c):
        result = [float('inf') for i in s]
        last_c = -float('inf')
        for i in range(len(s)):
            if s[i] == c:
                last_c = i
                result[i] = i-last_c
            else:
                result[i] = i-last_c
        last_c = float('inf')
        for i in range(len(s)-1, -1,-1):
            if s[i] == c:
                last_c = i
            result[i] = min(result[i], last_c - i)
        return result 

[zhangzz2015]

思路

• 最短距离，使用BFS。第一次遍历找到所有c的字符，放入queue。并设置初始化距离0。下面通过BFS遍历，一层一层设置其他字符的距离。复杂度O(N) + O(N)。空间复杂度O(N)。需要使用队列记录节点。

  关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {

        //  method 1 use queue and bft. 
        queue<int> que; 
        vector<int> ret(s.size(), INT_MAX); 
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]==c)
            {
                ret[i]=0; 
                que.push(i);
            }
        }
        while(que.size())
        {
            int topVal = que.front();
            que.pop();
            for(int i=-1; i<=1; i=i+2)
            {
                int newIndex = topVal +i; 
                if(newIndex<0 || newIndex>=s.size()) // skip; 
                    continue;                
                if(ret[topVal]+1 < ret[newIndex])
                {
                    que.push(newIndex);
                    ret[newIndex]=ret[topVal]+1;
                }
            }
        }        
        return ret; 

    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[thinkfurther]

思路

计算出c的所有位置，让s中的每个字符的位置相减，去最小值

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        index = 0
        locations = []
        for idx, letter in enumerate(s):
            if letter == c:
                locations.append(idx)

        indexes = range(len(s))
        difference = [ abs(x - locations[0]) for x in indexes]

        for i in range(1,len(locations)):
            difference = [ min(difference[x] , abs(x - locations[i])) for x in indexes]

        return difference

复杂度

Time: O(n*k) Space: O(k)

[Yufanzh]

Intuition

Traverse the array from left to right, and then right to left. Both sides will iterative using the following logic: initialize the location of c lastc as max_value, iterative through rray, if find char == c, then update lastc = i; else, update distance = lastc - i do the same from end to begin then the ans will be the minimum value comparing those two at each location.

Algorithm

code in python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        res = [0]*len(s)
        lastc = float('inf')
        for i, ch in enumerate(s):
            if ch == c:
                lastc=i
            else:
                res[i] = abs(lastc-i)
        for i in range(len(s))[::-1]:
            ch = s[i]
            if ch == c:
                lastc = i
            else:
                res[i] = min(res[i], abs(lastc-i))
        return res

Complexity analysis

time complexity: O(len(s) extra space complexity: O(1)

[HuijunXu]

思路

• 双指针

代码

var shortestToChar = function(s, c) {
    var l = -1;
    var n = -1;
    var i =0;
    var arr = [];
    while(i<s.length){
        if(n<=i){
            n++;
            while(s[n]!=c&&n<s.length){
                n++
            };
        }
        if(s[i]===c){
            l = i;
            arr[i]=0
        }else{
            if(l<0){
                arr[i] = Math.abs(i-n)
            }else if(n===s.length){
                arr[i] = Math.abs(i-l)
            } else{
                arr[i]=Math.min(Math.abs(i-l),Math.abs(i-n))
            }
        }
        i++
    }
    return arr
};

复杂度分析

时间：O(n) 空间：O(n)

结果

Accepted 76/76 cases passed (80 ms) Your runtime beats 79.89 % of javascript submissions Your memory usage beats 50.28 % of javascript submissions (40 MB)

[HackBL]

• 正反向遍历

  class Solution {
  public int[] shortestToChar(String s, char c) {
      int[] res = new int[s.length()];
      int k = -s.length();
  
      for (int i = 0; i < s.length(); i++) {
          if (s.charAt(i) == c) 
              k = i;
  
          res[i] = i - k;
      }
  
      for (int i = k; i >= 0; i--) {
          if (s.charAt(i) == c)
              k = i;
          res[i] = Math.min(res[i], k-i);
      }
  
      return res;
  }
  }

• Time: O(n)
• Space: O(1)

[nonevsnull]

思路

Array遍历

两次遍历

• 第一次从左到右，遇到c，将其右边的依次从1-m编号；直到遇到下一个c，重复编号过程。（第一个c左边为未编号状态）
• 第二次从右到左，遇到c，将其左边当前编号与预计编号比较并取min；第二次编号并会将第一个c左边的编号完成。

Stack 将s遍历一次

• 如果当前为c，
  • pop站内元素，并依次按距离递增编号；直到栈空或栈顶为c；当前位置编号0；将当前位置压入栈
• 如果当前不为c
  • 如果栈顶为c，那么当前位置编号1
  • 否则当前位置编号为前一个位置编号+1；
  • 将当前位置index 压入栈；

代码

//array遍历
class Solution {
    public int[] shortestToChar(String s, char c) {
        int pre = Integer.MIN_VALUE / 2;
        int[] res = new int[s.length()];
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == c) pre = i;
            res[i] = i - pre;
        }

        pre = Integer.MAX_VALUE;
        for(int i = s.length() - 1;i >= 0;i--){
            if(s.charAt(i) == c) pre = i;
            res[i] = Math.min(res[i], pre - i);
        }

        return res;
    }
}

//stack
class Solution {
    public int[] shortestToChar(String s, char c) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[s.length()];
        stack.add(0);
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == c){
                int pos = 0;
                while(!stack.isEmpty() && s.charAt(stack.peek()) != c){
                    int cur = stack.pop();

                    res[cur] = res[cur] == 0?++pos:Math.min(++pos, res[cur]);
                }
                res[i] = 0;
                stack.add(i);
            } else {
                if(!stack.isEmpty() && s.charAt(stack.peek()) == c){
                    res[i] = 1;
                } else if(i > 0 && res[i-1] != 0) {
                    res[i] = res[i-1] + 1;
                }
                stack.add(i);
            }
        }

        return res;
    }
}

复杂度

Array遍历 O(s.length()); O(1)

Stack O(s.length()) O(N),维护一个栈。

[skinnyh]

Note

Record the occurrence of char c in a list c_idx. Then use two pointers i and p to iterate S and c_idx. For each i, compare the distance with p and p+1 until find the closest p.

The space complexity can be improved. Instead of saving the c positions, we can scan the S twice from left to right and from right to left. So that each char will be able to compare to the closest C on its left and right.

Solution1

    def shortestToChar(self, s: str, c: str) -> List[int]:
        res, c_idx = [], []
        for i, ch in enumerate(s):
            if ch == c:
                c_idx.append(i)
        p = 0
        for i in range(len(s)):
            while (p < len(c_idx) - 1 and abs(c_idx[p + 1] - i) < abs(c_idx[p] - i)):
                p += 1
            res.append(abs(c_idx[p] - i))
        return res

Time complexity: O(2N + K) where N is the length of s and K is occurrence count of c.

Space complexity: O(K) to save the char occurrence positions.

Solution2

    def shortestToChar(self, s: str, c: str) -> List[int]:
        n, c_idx = len(s), float('-inf')
        res = [n] * n
        for i in range(n):
            if s[i] == c: c_idx = i
            res[i] = min(res[i], abs(i - c_idx))
        for i in range(n)[::-1]:
            if s[i] == c: c_idx = i
            res[i] = min(res[i], abs(i - c_idx))
        return res

Time complexity: O(2N) where N = len(s)

Space complexity: O(1)

[pophy]

思路

• 暴力解
  • 从前遍历字符串中每一个char 到 target的距离， O(N^2)
• 优化解
  • 首先遍历字符串 找到target在字符串中的位置 并记录在index queue中
  • 设置两个指针 pre = MIN_VALUE 和 next = queue.peek()， 分别代表target在字符串中出现的前一个和后一个位置
  • 再次遍历字符串 当前距离 = Math.min(i-pre, next -i)
  • 果current Index == queue.peek(), pre = currentIndex, queue.poll()

Java Code

    public int[] shortestToChar(String s, char c) {
        int[] res = new int[s.length()];
        Queue<Integer> indexQueue = new LinkedList();
        for (int i=0; i<s.toCharArray().length;i++) {
            if (s.charAt(i) == c) {
                indexQueue.add(i);
            }
        }
        int pre = -1;
        for (int i=0; i<s.toCharArray().length;i++) {
            int next = indexQueue.peek();
            res[i] = pre < 0 ? Math.abs(next-i) : Math.min(Math.abs(i-pre),Math.abs(next-i));
            if (i == indexQueue.peek() && indexQueue.size() > 1) {
                pre = indexQueue.peek();
                indexQueue.poll();
            }
        }
        return res;
    }

时间 & 空间 复杂度

• O(n)
• O(n)

[BlueRui]

Algorithm

1. Work through the array from the left to find the closest char c to the right of each char in s.
2. Then work through the array from the right to find the closest char c to the left of each char in s.
3. Find the min distance of step 1 and 2.
4. Step 2 and 3 can be combined.

Complexity

• Time Complexity: We are going over the array exactly twice. O(N)
• Space Complexity: We can use the same output array, so no extra space. O(1)

Code

Language: Java

public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] result = new int[n];
        Arrays.fill(result, n);
        // Find closest c on the right of each char
        int cur = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != c) {
                continue;
            }
            while (cur <= i) {
                result[cur] = i - cur;
                cur++;
            }
        }

        // Update to get the closest c from both sides by comparing left side
        cur = n - 1;
        for (int i = n - 1; i >=0; i--) {
            if (s.charAt(i) != c) {
                continue;
            }
            while (cur >= i) {
                result[cur] = Math.min(result[cur], cur - i);
                cur--;
            }
        }
        return result;
    }

[mmboxmm]

@HuijunXu

思路

• 双指针

代码

var shortestToChar = function(s, c) {
    var l = -1;
    var n = -1;
    var i =0;
    var arr = [];
    while(i<s.length){
        if(n<=i){
            n++;
            while(s[n]!=c&&n<s.length){
                n++
            };
        }
        if(s[i]===c){
            l = i;
            arr[i]=0
        }else{
            if(l<0){
                arr[i] = Math.abs(i-n)
            }else if(n===s.length){
                arr[i] = Math.abs(i-l)
            } else{
                arr[i]=Math.min(Math.abs(i-l),Math.abs(i-n))
            }
        }
        i++
    }
    return arr
};

复杂度分析

时间：O(n) 空间：O(n)

结果

Accepted 76/76 cases passed (80 ms) Your runtime beats 79.89 % of javascript submissions Your memory usage beats 50.28 % of javascript submissions (40 MB)

@HuijunXu

思路

• 双指针

代码

var shortestToChar = function(s, c) {
    var l = -1;
    var n = -1;
    var i =0;
    var arr = [];
    while(i<s.length){
        if(n<=i){
            n++;
            while(s[n]!=c&&n<s.length){
                n++
            };
        }
        if(s[i]===c){
            l = i;
            arr[i]=0
        }else{
            if(l<0){
                arr[i] = Math.abs(i-n)
            }else if(n===s.length){
                arr[i] = Math.abs(i-l)
            } else{
                arr[i]=Math.min(Math.abs(i-l),Math.abs(i-n))
            }
        }
        i++
    }
    return arr
};

复杂度分析

时间：O(n) 空间：O(n)

结果

Accepted 76/76 cases passed (80 ms) Your runtime beats 79.89 % of javascript submissions Your memory usage beats 50.28 % of javascript submissions (40 MB)

Nice, Three Pointers!!

[yingliucreates]

link:

https://leetcode.com/problems/shortest-distance-to-a-character/

知识弱点：

• nested for loops (eg. i & j): how it works is that 到 i 某一个 index, 遍历一遍 j 的所有 indices,然后再移到 i 的下一个 index

（抄）思路 （没有自己做出来，看的别人的答案）:

• 先把 c 找出来，把 c 的 indices 存入数组；
• 遍历整个数组，每一个 index 与 c 对应的 index 求绝对值到差， 来找到每一个 index 与最近一个 c 的 距离；
• 把这些距离存入新的空数组

代码 Javascript

const shortestToChar = function (s, c) {
  const indices = [];
  const distances = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === c) {
      indices.push(i);
    }
  }

  for (let i = 0; i < s.length; i++) {
    let min = Number.MAX_SAFE_INTEGER;
    for (let j = 0; j < indices.length; j++) {
      let distance = Math.abs(indices[j] - i);
      if (distance < min) {
        min = distance;
      }
    }
    distances.push(min);
  }

  return distances;
};

复杂度分析

时间 O(n2)

空间 不会算

[pangjiadai]

思路和复杂度

• 暴力：遍历两遍，先遍历一遍记录下target的index -> index_list，再遍历第二遍得到最小值
• 可以优化的地方：遍历第二遍:
  1. 可以遍历index_list记录最小值 O(n^2);
  2. 可以用一个指针标记最近的target O(N)

Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        # 两遍遍历
        index_list = []
        ans = []
        min_distance = len(s)
        for index, char in enumerate(s):
            if char == c:
                index_list.append(index)

        for index, char in enumerate(s):
            for i in range(0, len(index_list)):
                distance = abs(index-index_list[i])
                min_distance = min(distance, min_distance)
                if i == len(index_list) -1:
                    ans.append(min_distance)
                    min_distance = len(s)

        return ans

[zol013]

two pointers: for each character in the string we initialize two points L and R before and after the current character. Then we decrease the left pointer and increase the right pointer until the target character is found on the left side and right side of the current character. Then we record the minimum of the two distances. Python 3 code:

class Solution:
     def shortestToChar(self, s: str, c: str) -> List[int]:
           ans = []
           for i in range(len(s)):
                left_val = len(s)
                right_val = len(s)
                if s[i] == c:
                   ans.append(0)
                   continue
                l , r = i - 1, i + 1
                while r <= len(s)-1:
                         if s[r] == c:
                            right_val = r - i
                            break
                         else:
                               r += 1
                while l >= 0:
                         if s[l] == c:
                           left_val = i - l
                           break
                         else:
                               l -= 1
               ans.append(min(left_val, right_val))
           return ans

Time complexity O(n^2) we scan through the string twice. Space Complexity O(n) we record the distances in an list 'ans'

[zjsuper]

idea: iterate the string, use dictionary to save the distance and update

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        dic = {c:[]}
        lens = len(s)
        output = []
        for i in range(lens):
            if s[i] == c:
                dic[c].append(i)
        for i in range(lens):
            temp = [abs(i-k) for k in dic[c]]
            output.append(min(temp))
        return output

[ningli12]

思路 - Array遍历

• 初始化result array.
• 两次遍历
• 第一次从左到右，遇到c，将其右边的依次从 i - pre。 pre不会超过Array的长度
• 第二次从右到左，遇到c，将其左边 i - pre 比较并取min；

代码

class Solution {
  public int[] shortestToChar(String S, char C) {
        int n = S.length(), pre = -n, res[] = new int[n];
        for (int i = 0; i < n; i++) {
            if (S.charAt(i) == C) pre = i;
            res[i] = i - pre;
        }
        for (int i = pre - 1; i >= 0; i--) {
            if (S.charAt(i) == C)  pre = i;
            res[i] = Math.min(res[i], pre - i);
        }
        return res;
    }
 }

思路 - DP

• Array遍历
• 初始化result array.
• 遍历从左到右，遇到c，设为0，其余设为 size - 1;
• 遍历从左1到右(i = 1)，和前一位（i - 1） + 1比较后取最小值
• 遍历从右1到左（i = size - 2），和前一位（i + 1） + 1比较后取最小值

class Solution {
    public int[] shortestToChar(String s, char c) {
        int size = s.length();
        int[] res = new int[size];
        for(int i = 0; i < size; i++){
            res[i] = s.charAt(i) == c? 0: size - 1;
        }

        for (int i = 1; i < size; i++){
            res[i] = Math.min(res[i], res[i - 1] + 1);
        }

        for (int i = size - 2; i >= 0; i--){
            res[i] = Math.min(res[i], res[i + 1] + 1);
        }

        return res;
    }
}

复杂度：

Time: O(n) Space: O(n)

[bolunzhang2021]

java, 菜鸡解法

import java.util.ArrayList;
import java.util.*;
class Solution {
    public int[] shortestToChar(String s, char c) {
       char []arr=s.toCharArray();
        int[]ans=new int[arr.length];
      ArrayList<Integer> a=new ArrayList<Integer>();

        for(int i=0; i<arr.length; i++)
        {
            if(arr[i]==c)
                a.add(i);
        }
        for(int i=0; i<arr.length;i++)
        {
        ArrayList<Integer> list = new ArrayList<Integer>(); 
            for(int j=0;j<a.size();j++)
            {
               list.add(Math.abs(i-a.get(j)));
            }
             ans[i]=Collections.min(list);
        }
              return ans;
    }
}```
时间复杂度o(n^2)
空间复杂度0（n）

[Laurence-try]

思路

新建一个数组长度为n (n 是input数组的长度)， 并把里面所有elements设为n。 正向遍历一遍， 在新建的数组里面更新第一个字母出现以后的所有distance，如果再次遇见字母，distance归0。 然后在反向遍历一遍，覆盖刚刚新建的数组，同样从第一个字母出现以后开始覆盖，覆盖的条件是此时的distance要小于上一步更新的distance， 同样如果遇见字母，distance归0。

代码

使用语言：Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        res = [len(s) for x in range (len(s))]
        p = 0
        count = 0
        flag = False
        while p < len(s):
            if s[p] == c:
                flag = True
                count = 0
                res[p] = 0
            else:
                if flag:
                    count += 1
                    res[p] = count
            p += 1
        count = 0
        flag = False
        p -= 1
        while p >= 0:
            if s[p] == c:
                flag = True
                count = 0
                res[p] = 0
            else:
                if flag:
                    count += 1
                    if res[p] > count:
                        res[p] = count
            p -= 1
        return res

复杂度分析 时间复杂度：O(n) 空间复杂度：O(1), compensate O(n)

[simonsayshi]

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {

        vector<int>arr;int Last_Occ=-1;
        int l;
        for(int j = 0 ; j < s.length() ; j++)
        {
            size_t k = s.find(c,j);  
            if(j==k)//found c at index j
            {
                arr.push_back(0);
                Last_Occ=k;//store the latest index of occurence of char c
            }
            else{
                if(Last_Occ==-1)//not reached index 'j' yet where s[j] == c
                    arr.push_back(k-j);
                else
                {
                /* use  l = min(k - j , j - Last_Occ) */
                    if( k - j <= j - Last_Occ)
                        l = k - j;
                    else
                        l = j - Last_Occ;
                    arr.push_back(l);
                }
            }

        }
        return arr;
    }
};

[tongxw]

思路

正序遍历，计算每个位置到左侧指定字符的最短距离； 倒序遍历，计算每个位置到右侧指定字符的最短距离； 取最小值。

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
  let ans = new Array(s.length);
  let count = s.length;
  for (let i=0; i<s.length; i++) {
    count = s[i] === c ? 0 : count + 1;
    ans[i] = count;
  }

  count = s.length;
  for (let i=s.length-1; i>=0; i--) {
    count = s[i] === c ? 0 : count + 1;
    ans[i] = Math.min(ans[i], count);
  }

  return ans;
};

复杂度分析

• 时间复杂度：O(s.length)
• 空间复杂度：O(s.length)

[zzhsaga]

Code

public class test {
    public static int[] shortestToChar(String s, char c) {
        int l = s.length();
        int[] ans = new int[l];
        int prev = -10000;
        for (int i = 0; i < l; i++){
            if(s.charAt(i) == c){
                prev = i;
            }
            ans[i] = i-prev;
        }
        prev = 10000;
        for (int i = l - 1; i >=0; i--){
            if(s.charAt(i) == c){
                prev = i;
            }
            ans[i] = Math.min(prev - i, ans[i]);
        }
        return ans;
    }

Complexity Analysis

• TC: O(n)
• SC: O(n)

[FlorenceLLL]

先写一个自己想出来的暴力解决方法

思路

1.首先找到c的所有位置，存在indexList数组中 2.遍历s每个index - indexList的值，取最小，存到answer中

代码

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        ##找出所有c的位置
        index = s.find(c)
        indexList = []
        indexList.append(index)

        while (index != -1):
            index = s.find(c,index + 1)
            if(index != -1):
                indexList.append(index)

        ##计算s每个位置 - c所有的位置，取最小，存到list中
        answer = []
        for i in range(len(s)):
            min = abs(i - indexList[0])
            for j in range(len(indexList)):
               if(abs(i-indexList[j]) < min):
                   min = abs(i-indexList[j])
            answer.append(min)

        return answer

复杂度分析

时间复杂度 $$O(n^2)$$ 因为循环两次 空间复杂度 $$O(n)$$ 因为新建了一个数组存answer

[Mahalasu]

思路

Naive Way

遍历一遍找出所有的c所在的地方，然后遍历第二遍，将每一个字母与所有c所在的位置进行位置计算，取最短的一个

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        places = []
        result = [float('inf') for _ in range(len(s))]

        for idx in range(len(s)):
            if s[idx] == c:
                places.append(idx)

        for idx in range(len(s)):
            for cidx in places:
                dist = abs(idx - cidx)
                if abs(idx - cidx) < result[idx]:
                    result[idx] = dist

        return result

T：O(MN) S：O(M) N为s长度，M为c所在的所有位置的个数

正序倒序遍历

正序遍历得到每个位置到其左侧最近位置的距离，然后倒序遍历得到每个位置到其右侧最近位置的距离

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        length, pos = len(s), float('inf')
        result = [length] * length

        for i in list(range(length)) + list(range(length)[::-1]):
            if s[i] == c:
                pos = i
            result[i] = min(result[i], abs(i - pos))

        return result

T: O(N) S: O(N)

[xieyj17]

Step 1. 找到s 中所有c 在的位置

Step 2. 如果两个c 中间的间隔为d 并且 d % 2 == 0， 那个它们离最近的c 的距离就是1,2,...,d//2, d//2, ..., 2, 1,如果d 是奇数那么距离就是 1,2,...,d//2, d//2+1, d//2, ..., 2, 1

Step 3. 两端分别处理一下

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        def gen_interval(k):
            if k%2 != 0:
                l = k//2 + 1
                return [i for i in range(1, l)] + [i for i in range(l, 0, -1)]
            else:
                l = k//2
                return [i for i in range(1, l+1)] + [i for i in range(l, 0, -1)]

        locs = []
        for i in range(len(s)):
            if s[i] == c:
                locs.append(i)
        if len(locs) == 0:
            res = [i for i in range(locs[0],-1,-1)] + [i for i in range(len(s)-1-locs[0])]
        else:
            diffs = [locs[i+1] - locs[i] - 1 for i in range(len(locs)-1)]
            res = [i for i in range(locs[0],0,-1)]
            for d in diffs:
                res += ([0] + gen_interval(d))
            res += [i for i in range(len(s)-locs[-1])]
        return res

Time: O(n)

Space: O(n)

[chenming-cao]

解题思路

遍历两次字符串：第一次正向遍历，计算每个字符和前面出现的特殊字符的最近距离；第二次反向遍历，计算每个字符和后面出现的特殊字符的最近距离。两次遍历过程中，把最短距离写入整数数组中。

代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        int length = s.length();
        int[] res = new int[length]; // create int array with size of the length of string
        Arrays.fill(res, length); // initialize the array and fill with the length of string (the distance between two characters is always smaller than the length of string)

        int idx = 0;
        // traverse the array, and update the distance
        for (int i = s.indexOf(c); i < length; i++) {
            if (s.charAt(i) == c) idx = i;
            if (Math.abs(idx - i) < res[i]) res[i] = Math.abs(idx - i);
        }
        // traverse the array in reverse order, and update the distance
        for (int j = s.lastIndexOf(c); j >= 0; j--) {
            if (s.charAt(j) == c) idx = j;
            if (Math.abs(idx - j) < res[j]) res[j] = Math.abs(idx - j);
        }

        return res;
    }
}

复杂度分析

令n为字符串长度

• 时间复杂度：O(n)，循环运行次数
• 空间复杂度：O(1)，除了返回的数组外，其他操作需要常数空间

[devosend]

思路

遍历两次字符串，找到当前字符距离左边和右边第一个目标字符的距离，存储较小的值

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        ans = []
        index = -len(s)

        for i in range(len(s)):
            if s[i] == c:
                index = i

            ans.append(i - index)

        # index = len(s)
        for i in range(len(s) - 1, -1, -1):
            if s[i] == c:
                index = i

            ans[i] = min(ans[i], abs(index - i))

        return ans

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[HZHENGZHI]

思路 每一次都查找到距离当前字符最近的字符c的位置，进行相减处理。当减到自己为0后，查找下一个字符c所在位置 代码

public int[] shortestToChar(String s, char c) {
        int []ans=new int[s.length()];
        char chars[]=s.toCharArray();
        int j=0;
        int temp=0;
        for (int i = 0; i < chars.length; i++) {
            while (j<chars.length &&chars[j]!=c  )
            {
                j++;
            }
            if(i-j!=0)
            {
                if(j<chars.length && chars[temp]==c &&chars[j]==c)
                {
                    ans[i]=Math.min(Math.abs(temp-i),Math.abs(j-i));

                }
                else if(j<chars.length && chars[j]==c)
                {
                    ans[i]=Math.abs(i-j);
                }
                else if(chars[temp]==c)
                {
                    ans[i]=Math.abs(temp-i);
                }
            }
            if(i-j==0)
            {
                ans[i]=0;
                temp=j;
                j++;
            }
        }
        return ans;
    }

复杂度

• 空间复杂度$O(n)$
• 时间复杂度$O(n*m)$

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
public int[] shortestToChar(String s, char c) {
        int l = Integer.MIN_VALUE + s.length() + 1;
        int r = s.indexOf(c);
        int[] res = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (i <=  r){
                res[i] = Math.min(i - l, r - i);
            }else {
                l = r;
                r = s.indexOf(c, l + 1) == -1 ? Integer.MAX_VALUE : s.indexOf(c, l + 1);
                res[i] = Math.min(i - l, r - i);
            }
        }
        return res;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$