【Day 2 】2021-12-13 - 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 中的所有字母均为小写字母。

[yan0327]

思路： 字符的最短距离，可以从前往后遍历，以及从后往前遍历求最小值。 初始化一个out数组 令flag = -1 ，flag表示前一个字符c出现的位置。 从前往后遍历：（1）判断是否该字符为c （2）若c存在【flag >= 0】则此时out[i] = i-flag 否则 out[i] = math.MaxInt32 从后往前遍历：（1）判断是否该字符为c （2）若c存在【flag >= 0】则此时out[i] = min（out[i]，flag-i） 第二次遍历记得比较大小，为了得到最优解。求个最小值。 最后题目出问题的地方是：flag >= 0 考虑 字符c在第一个的情况！

func shortestToChar(s string, c byte) []int {
    out := make([]int,len(s))
    flag := -1
    for i :=0;i<len(s);i++{
        if s[i] == c{
            flag = i
        }
        if flag >= 0{
            out[i] = i-flag
        }else{
            out[i] = math.MaxInt32
        }
    }
    flag = -1
    for i := len(s)-1;i>=0;i--{
        if s[i] == c{
            flag = i
        }
        if flag >= 0{
            out[i] = min(out[i],flag-i)
        }
    }
    return out
}
func min(a,b int)int{
    if a < b{
        return a
    }
        return b
}

时间复杂度O（N） 空间复杂度O（N）

[zwx0641]

思路： 从前往后从后往前两次遍历 tmp记录c出现的位置 第一次遍历ans[i]存放s中i位置字符与前一个c的距离 第二次遍历比较min(ans[i], s中i位置字符与后一个c的距离)

class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] ans = new int[s.length()];
        //Arrays.fill(ans, s.length() + 1);
        int i = 0, j = s.length() - 1, tmp = -1;
        while (i < s.length()) {
            if (s.charAt(i) == c) {
                ans[i] = 0;
                tmp = i;
            } 
            if (tmp != -1) {
                ans[i] = i - tmp;
            } else {
                ans[i] = s.length() + 1;
            }

            i++;
        }
        tmp = -1;
        while (j >= 0) {
            if (s.charAt(j) == c) {
                ans[j] = 0;
                tmp = j;
            }
            if (tmp != -1) ans[j] = Math.min(ans[j], tmp - j);

            j--;
        }

        return ans;
    }
}

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

[Husky-Gong]

解题思路

• 使用两个指针，代表一个window，左边设为left，右边设置为right
• curr代表当前遍历到的S的位置
• 分为三个阶段： -- 初始化：left未进入S，right为第一个e出现的位置 -- 中间阶段：left和right均为S中的某一个位置 -- 最后阶段：left为S中最后一个e出现的位置，right已发生越界

• 需要注意： -- 每次curr扫描到一个C，代表其已到达window的右边界，则需要将左边界设置为C当前位置，并且重新设定右边界 -- 更新距离时，需要使用Math.min(Math.abs(curr - left), Math.abs(curr - right))求出最小值gap，设置到结果位置result[curr] = gap -- 不能设置为Integer.MIN_VALUE 和Intger.MAX_VALUE，因为会发生越界

  代码

  public static int[] minGap(String S, Character C) {
      // set window [left, right] range
      int left = -S.length();
      int right = 0;
  
      // initialize right first
      while (right < S.length() && S.charAt(right) != C) {
          right++;
      }
  
      // curr -> current position
      int curr = 0;
      int[] distance = new int[S.length()];
  
      while (curr < S.length() && right < S.length()) {
          if (S.charAt(curr) == C) {
              distance[curr] = 0;
              // it means curr has reached to the right edge of the window
              // then have to update the left, right for a new window
              left = curr;
              while (left == right || (right < S.length() && S.charAt(right) != C)) {
                  right++;
                  // if right is out of S, then set it as 2 * S.length()
                  if (right == S.length()) {
                      right = 2 * S.length();
                  }
              }
          } else {
              // between current window
              // update gaps for Characters in this window
              int gap = Math.min(Math.abs(curr - left), Math.abs(right - curr));
              distance[curr] = gap;
          }
          curr++;
      }
  
      return distance;
  }

  复杂度

  时间复杂度：O(n) 从左到右，只遍历一遍 空间复杂度：O(n) 需要开辟新的空间，存储结果

[Alfie100]

正向遍历 + 反向遍历

LeetCode 原题连接：821. 字符的最短距离

思路

对于每个字符 s[i] 找出其距离左边及右边下一个目标字符 C 的距离，左右距离中的较小值即为答案。

从左往右遍历： 假设上一个 C 出现的位置为 pre，则当前 i 位置的字符距离 $C$ 的距离为 i-pre （pre <= i）；

从右往左遍历： 假设上一个 C 出现的位置为 pre，则当前 i 位置的字符距离 C 的距离为 pre-i （i <= pre）；

代码 【Python】

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

        n = len(s)
        ans = []

        # 正序遍历
        pre = -n    # 设为较小的 -n 即可（距离的最大值不可能超过n）
        for (i, ch) in enumerate(s):
            if ch == c:
                pre = i
            ans.append(i-pre)

        # 逆序遍历
        pre = 2*n   # 设为较大的 2*n 即可（距离的最大值不可能超过n）
        for i in range(n-1, -1, -1):
            if s[i] == c:
                pre = i
            ans[i] = min(ans[i], pre-i)

        return ans

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符 s 长度。

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

[wxj783428795]

思路

第一次循环：找到s中所有c的下标。 第二次循环：循环对比s中每个字符，到所有c的下标的距离，取其中的最小值放入answer中

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */

var shortestToChar = function (s, c) {
    let indexs = []; // 存储所有c在s中的下标
    let answer = []; // 存储结果
    for (let i = 0; i < s.length; i++) { // 第一遍循环先找到所有c在s中的下标
        if (c === s[i]) {
            indexs.push(i)
        }
    }
    for (let i = 0; i < s.length; i++) { // 第二遍循环
        let distance = 0;
        if (c === s[i]) { // 如果当前位等于c，则将0放入answer
            answer.push(distance)
        } else {
            distance = Math.abs(i - indexs[0]);
            for (let j = 1; j < indexs.length; j++) {// 循环判断当前位和每一个c的距离，取最小值
                distance = Math.min(distance, Math.abs(i - indexs[j]));
            }
            answer.push(distance)
        }
    }
    return answer;
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

• 时间复杂度：O(NM)，其中 N 为s的长度，M为s中c出现的次数。
• 空间复杂度：O(N+M)，其中 N 为s的长度，M为s中c出现的次数。

[CodeWithIris]

思路

  初始化ans均为1.
  第一次遍历字符串s，将ans中对应字符c的位置设置为0.
  第二次遍历字符串s，遇到非字符c的便从左侧或者右侧寻找字符c，取最小值填入ans中.

代码

class Solution {
public:
    void findC(string& s, int i, char c, vector<int>& ans){
        int left = i - 1, right = i + 1, n = s.size();
        while(left >= 0 || right < n){
            if(left >= 0 && right < n){
                if(s[left] == c || s[right] == c){
                    ans[i] = right - i;
                    return ;
                }
            }else if(left >= 0 && s[left] == c){
                ans[i] = i - left;
                return ;
            }else if(right < n && s[right] == c){
                ans[i] = right - i;
                return ;
            }
            --left;
            ++right;
        }
    }
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        vector<int> ans(n, 1);
        for(int i = 0; i < n; ++i){
            if(s[i] == c) ans[i] = 0;
        }
        for(int i = 0; i < n; ++i){
            if(s[i] != c) findC(s, i, c, ans);
        }
        return ans;
    }
};

复杂度分析

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

[ZhangNN2018]

思路

先遍历s找到所有等于c的元素下标，并存在数组lab里，
再次遍历s计算所有元素的下标与数组lab里元素值的差的绝对值，取最小的一个。

代码

      class Solution(object):
      def shortestToChar(self, s, c):
          """
          :type s: str
          :type c: str
          :rtype: List[int]
          """
          lab=[]
          for i in range(len(s)):
              if s[i]==c:
                  lab.append(i)

          res=[0]*len(s)
          for i in range(len(s)):
              lab0 = [abs(j-i) for j in lab]
              res[i]=min(lab0)
          return res

复杂度

时间复杂度：O(NM), N为数组s的长度, M为数组lab的长度。
空间复杂度：O(M), M为数组lab的长度，最差情况下等于数组s的长度。

[wangzehan123]

• 语言支持：Java

Java Code:

public class Solution {
    /**
     * @param S: 
     * @param C: 
     * @return: nothing
     */
    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;
    }
}

[zhangzz2015]

思路

• f(i)为第i个位置的最短距离，f(i)和s字符串中在i 的前后最近的c 位置相关，有时候一次同时处理两个位置比较难，但是可分解成先处理前面的最近位置，再处理后面的最近位置则比较容易。实现方法，两次遍历，先从前往后，找到前面的最近位置，再从后往前，找到后面的最近位置，返回两次中最小的。时间复杂度为O(N)，空间复杂度为O(1)，不考虑输出的话。

关键点

代码

• 语言支持：C++

C++ Code:

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

        vector<int> ret(s.size(), INT_MAX); 
        // loop left. 
        int pos = -1; 
        for(int i=0; i< s.size(); i++)
        {
            if(s[i]==c)
            {
                pos = i; 
                ret[i] =0; 
            }
            else if(pos!=-1)
            {
                ret[i] = i - pos; 
            }
        }
        pos = -1; 
        for(int i= s.size()-1; i>=0; i--)
        {
            if(s[i]==c)
            {
                pos = i; 
                ret[i] =0; 
            }
            else if(pos!=-1)
            {
                ret[i] = min(ret[i], pos -i); 
            }
        }

        return ret; 

    }
};

[zwmanman]

思路

Iterate s and store index of c in a dictionary Iterate s again and calculate the min diff of c index in dictionary

代码

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        dictC = {}
        dictC[c] = []
        res = []

        for i in range(len(s)):
            if s[i] == c:
                dictC[c].append(i)

        for i in range(len(s)):
            res.append(min([abs(i - ele) for ele in dictC[c]]))

        return res

复杂度分析

• 时间复杂度：O(NM)，其中 N 为数组长度, M为dictionary长度。
• 空间复杂度：O(N)

[SHAO-Nuoya]

思路

正向及反向遍历 注意初始时第一个c的位置的设定

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n =  len(s)
        left = float('-inf')
        ans = [0 for _ in range(n)]
        for i in range(n):
            if s[i] == c:
                left = i
                ans[i] = 0
            else:
                ans[i] = i - left

        right = float('inf')
        for i in range(n-1, -1, -1):
            if s[i] == c:
                right = i
            else:
                ans[i] = min(right -i, ans[i])

        return ans

[q815101630]

遍历两遍array， 从左往右+从右往左。

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

        idx = float("inf")
        for i,v in enumerate(s):
            if v == c:
                idx = i
            else:
                if idx != float("inf"):
                    ans[i] = i-idx

        idx = float("inf")

        for i in range(len(s)-1, -1, -1):
            if s[i] == c:
                idx = i
                ans[i] = 0
            else:
                if idx != float("inf"):
                    ans[i] = min(ans[i], idx-i)

        return ans

时空O(n)

[Menglin-l]

1. Determine the distance to the nearest c on the left.

Traverse s from left to right and count the index from the maximum, the size of s, as the distance.

Increase the next index by one. If c occurs, change the distance to zero.

2. Determine the distance to the nearest c on the right.

Traverse s from right to left. Count the index and compare it with the previous value, then take the minimum.

---

class Solution {
    // s = "l  o  v  e  l  e  e  t  c  o  d  e", c = "e", s.length() = 12
    //     12 13 14  0  1  0  0  1  2  3  4  0 
    //      3  2  1  0  1  0  0  1  2  2  1  0
    public int[] shortestToChar(String s, char c) {
        if (s.length() == 1) return new int[]{0};

        char[] cc = s.toCharArray();// O(N)
        int[] res = new int[s.length()];// O(N)
        int disLeft = s.length();
        int disRight = s.length();

        // O(N)
        for (int i = 0; i < cc.length; i ++) {
            if (cc[i] == c) {
                disLeft = 0;
            }
            res[i] = disLeft;
            disLeft ++;
        }

        // O(N)
        for (int j = cc.length - 1; j >= 0; j --) {
            if (cc[j] == c) {
                disRight = 0;
            }
            res[j] = Math.min(res[j], disRight);
            disRight ++;
        }
        return res;
    }
}

---

Time: O(N)

Space: O(N)

[rzhao010]

Thoughts

1. Get all indices of c, go through s to compare i with indices of c
2. Traverse s from head and tail side, record the last index of c , so i - prev and prev - i is the distance for each traverse, at last compare and select the smaller one

Code

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

    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] res = new int[n];
        // in case out of boundry 
        int prev = Integer.MIN_VALUE / 2;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                prev = i;
            }
            res[i] = i - prev;
        }
        prev = Integer.MAX_VALUE / 2;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                prev = i;
            }
            res[i] = Math.min(prev - i, res[i]);
        }
        return res;
    }

Time Complexity

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

[SenDSproject]

解题思路：

方法1：

遍历列表两次，第一次遍历的时候储存所有c字符出现的位置，第二次遍历计算距离c字符下标的距离

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        #pos 储存每个c出现的位置
        pos, res = [],[]
        for i in range(len(s)):
            if s[i]==c:
                pos.append(i)

        #p指针在pos数组
        p =0
        # 再次遍历字符串
        for i in range(len(s)):
            # 如果当前i 小于pos[0],说明这个字符出现在第一个c字符的前面
            # 那么直接用pos[0] - i 
            #这里pos[0] 储存的是character c 在S中出现的下标， 所以可以直接减
            if i < pos[0]:
                res.append(pos[0]-i)
            # 如果当前i大于pos最后一个位置，说明这个字符出现在最后一个c字符的后面
            #那么直接用i-pos[-1]
            elif i > pos[-1]:
                res.append(i - pos[-1])
            # 如果就是字符就是c，那么数值为0，同时给p+1 为下一步做准备
            elif i == pos[p]:
                res.append(0)
                p+=1
            ##在两个c之间，所以返回距离的最小值
            else:
                res.append(min(pos[p]-i,i-pos[p-1]))
        return res

时间复杂度O(N) 空间复杂度O(N)

[XinnXuu]

Notes

Traverse the string twice, one from left to right, and one from right to left.

Code (Java)

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] res = new int[n]; 
        //left to right
        int right = -10001;
        for (int i = 0; i < n; i++){
            res[i] = i - right;
            if (s.charAt(i) == c){
                res[i] = 0;
                right = i;
            }
        }
        //right to left
        int left = 10001;
        for (int i = n - 1; i >= 0; i--){
            if (res[i] > left - i){
                res[i] = left - i;
            }
            if (s.charAt(i) == c){
                res[i] = 0;
                left = i;
            }
        }
        return res;
    }
}

Complexity

• Time: O(N), N is the length of string s.
• Space: O(N)

[ForLittleBeauty]

思路

---

1. scan the list from left to right, when find c set the index = the position of c, so that our result array can record the distance between a character and the c show before that character.
2. scan the list from right to left, change index whenever encounter a c. make record[i] = min(abs(i-index),record[i])

---

代码

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

        index = 0
        for i in range(len(s)-1,-1,-1):
            if s[i]==c:
                index = i
            result[i] = min(result[i],abs(index-i))
        return result

---

时间复杂度: O(n)

空间复杂度: O(n)

[ZacheryCao]

Idea

Array to record position of the C.

Code

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

        ans = []
        p1, p2 = math.inf, math.inf
        if len(pos) == 1:
            p1 = 0
        else:
            p1 = 0
            p2 = 1
        for i in range(len(s)):
            if p2 != math.inf and i > pos[p2] and p2<len(pos)-1:
                p1 += 1
                p2 += 1
            if i <= pos[p1] or  p2 == math.inf:
                ans.append(abs(pos[p1] - i))
            else:
                ans.append(min(abs(i - pos[p1]),abs(pos[p2] - i) ))
        return ans

Complexity:

Time: O(N) Space: O(N)

[Courtneyz94]

class Solution(object):
    def shortestToChar(self, S, C):
        prev = -len(S)
        ans = []
        for i in range(len(S)):
            if S[i] == C: 
                prev = i
            ans.append(i - prev)

        prev = 2 * len(S)
        for i in range(len(S) - 1, -1, -1):
            if S[i] == C: 
                prev = i
            ans[i] = min(ans[i], prev - i)

        return ans

time complexity: o(n) space complexity: o(1)

[yangziqi1998666]

Greedy, pointer

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)

[BlessingLR]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        pos = [-float('inf')]
        for idx, char in enumerate(s):
            if char == c:
                pos.append(idx)
        pos.append(float('inf'))
        i = 1
        res = []
        for idx, char in enumerate(s):
            if idx == pos[i]:
                i += 1
                res.append(0)
                continue
            res.append(min(pos[i]-idx, idx-pos[i-1]))
        return res

[zol013]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [float('inf') for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                if s[j] == c:
                    ans[i] = j - i
                    break

        for i in range(n-1,-1,-1):
            for j in range(i,-1,-1):
                if s[j] == c:
                    ans[i] = min(ans[i],i-j)
                    break
        return ans

[yijing-wu]

思路

iterate twice, from left to right, then from right to left, always update the shortest distance

代码

class Solution {
    public int[] shortestToChar(String s, char c) {

        int len = s.length();
        int loc = -20000;   // -2*10^4
        char[] ch = s.toCharArray();

        int[] ans = new int[len];

        // from left to right
        for(int i = 0; i < len; ++i) {
            if( ch[i]  == c ) {
                loc = i;
                ans[i] = 0;
            } else {
                ans[i] = i - loc;
            }
        }

        // from right to left
        for(int i = len - 1; i >= 0; --i) {
            if( ch[i]  == c ) {
                loc = i;
            } else {
                ans[i] = Math.min(ans[i], Math.abs(loc - i));
            }
        }

        return ans;
    }
}

复杂度分析

• Time Complexitty = O(N)
• Space Complexitty = O(N)

[Frederickfan]

Idea:

We can set a left pointer pointing to the left occurrence of the character c and set a right pointer pointing to the right occurrence of the character c. Then we iterate the array, for each element we encountered, we check the distance between itself and the left pointer and also check the distance between itself and the right pointer. The minimum one of those two distances will be the result for the current character.

Code:

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        n = len(s)
        l = 0 if s[0] == c else n
        r = s.find(c, 0)
        res = [0 for _ in range(n)]

        for i in range(n):
            res[i] = min(abs(i - l), abs(r - i))

            if i == r:
                l = r 
                r = s.find(c, l + 1)

        return res

Complexity

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

[moirobinzhang]

思路： 从前往后 以及 从后往前两次遍历 第一次遍历result[i]记录i位置字符与前一个c的距离 第二次遍历result[i]比较Min(result[i], i位置字符和后一个c的距离）

代码： class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: result = []

    flag_index = len(s) - 1        
    for i in range(len(s)):
        if (s[i] == c):
            flag_index = i
        result.append(abs(flag_index - i))

    flag_index = 0
    for i in range(len(s) -1, -1, -1):
        if (s[i] == c):
            flag_index = i
        result[i] = min(result[i], abs(flag_index - i ))

    return result

复杂度分析: 时间复杂度O（N） 空间复杂度O（N）

[cszys888]

思路

1. 扫描s，记录c出现的位置，存在叫做locations的list里面
2. 遍历locations里面记录的位置，根据每个位置去计算它周围与它距离最近的点的距离。这个过程也会正好遍历一次s字符串

代码

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

        result = []
        for i in range(locations[0]):
            result.append(abs(locations[0] - i))
        for idx in range(1, len(locations)):
            mid = (locations[idx]+locations[idx - 1])//2
            for i in range(locations[idx-1],mid+1):
                result.append(abs(locations[idx-1] - i))
            for i in range(mid+1,locations[idx]):
                result.append(abs(locations[idx] - i))
        for i in range(locations[-1], n):
            result.append(abs(locations[-1] - i))

        return result

复杂度分析

时间复杂度：O(N) 空间复杂度: O(N)

[ginnydyy]

Problem

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

Note

• Intuition: scan once and mark all the c index. scan again to calculate the distance comparing the marked index.
• Improvement: scan once from left to right and calculate the initial distance. scan again from right to left and update the distance. Note that from left to right, need to use Integer.MIN_VALUE / 2 to avoid overflow.

Solution

class Solution {
    public int[] shortestToChar(String s, char c) {
        if(s == null || s.isEmpty()){
            return null;
        }

        int[] res = new int[s.length()];

        int left = Integer.MIN_VALUE / 2;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == c){
                left = i;
            }
            res[i] = Math.abs(i - left);
        }

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

        return res;
    }
}

Complexity

• T: O(n) n is the length of s.
• S: O(1) no extra space is required.

[guangsizhongbin]

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

    // 从左向右遍历, 记录c出现的前一个位置，保存 i - prev
    prev := math.MinInt32 / 3
    for i := 0 ; i < n; i ++ {
        if s[i] == c {
            prev = i
        }
        res[i] = i - prev
    }

    // 从右向左遍历, 记录c出现的前一个位置，保存 prev - i
    prev = math.MaxInt32 / 3
    for i := n - 1; i >= 0; i --{
        if s[i] == c {
            prev = i
        }
        res[i] = min(res[i] , prev - i)
    }

    return res
}

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

[Laurence-try]

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

[chakochako]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        prev = float('-inf')
        ans = []
        for p, v in enumerate(s):
            if v == c:
                prev = p
            ans.append(p - prev)

        prev = float('inf')
        for i in range(len(s) - 1, -1, -1):
            if s[i] == c: 
                prev = i
            ans[i] = min(ans[i], prev - i)

        return ans

[1052561252]

思路

暂时只能想到时间复杂度为O(n*m)的解法，想不到有哪些性能更优的解法，先解出来再说吧 1.通过字符串s生成字符串数组chars，遍历chars，获得c在chars中的位置，通过list存储 2.再次遍历chars，如果chars[i]!=c，将i与list中保存的值进行判断，找出最小的差值并保存到answer[i]中

代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        char[] chars = s.toCharArray();
        int[] answer = new int[chars.length];

        List<Integer> tags = new ArrayList<>();
        //遍历chars，标记c在chars中的各个位置
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == c) {
                tags.add(i);
            }
        }

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != c) {
                int min = 200;
                for (Integer tag : tags) {
                    min = Math.min(min, Math.abs(i - tag));
                }
                answer[i] = min;
            }
        }

        return answer;
    }
}

复杂度

时间复杂度：O(n*m) n:s的长度 m:list的长度

空间复杂度：O(n+m)

[AlvinZhouOops]

Class Solution:
    def getDisFromStr(self, String, C):
        n = len(String)
        res = [n for _ in range(n)]
        l = r = 0
        for r in range(n):
            if String[r] == C:
                while l <= r:
                    res[l] = r - l
                    l += 1
       r = n -1
       for l in range(n-1, -1, -1):
           if String[l] == C:
               while r >= l:
                   res[r] = min(res[r], r-l)
                   r -= 1
      return res

[feifan-bai]

思路

1. Traverse from left to right, record the last position where c appears, ans_l = i - prev_l
2. Traverse from right to left, record the last position where c appears, ans_r = prev_r - i
3. Final ans = min(ans_l, ans_r)

### 代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        prev_l,  prev_r = float('-inf'), float('inf')
        ans = []

        for i, char in enumerate(s):
            if char == c:
                prev_l = i
            ans.append(i - prev_l)

        for i in range(len(s)-1, -1, -1):
            if s[i] == c:
                prev_r = i
            ans[i] = min(ans[i], prev_r - i)

        return ans

• 复杂度分析
• 时间复杂度：O(N), N = len(s)
• 空间复杂度：O(N), N = len(ans)

[hdyhdy]

思路：两次遍历，前后遍历，设立更新目标字符的位置。然后在两次遍历得出的相对位置中找到最小值。

func shortestToChar(s string, c byte) []int {
    n := len(s)
    res := make([]int, n)
    left, right := math.MinInt32/2, math.MaxInt32/2

    for i :=0; i < n ;i++ {
        if s[i] == c{
            left = i
        } 
        res[i] = i - left
    }
    for i := n-1;i >= 0;i -- {
        if s[i] == c {
            right = i
        }
        res[i] = min(res[i], right-i)
    }
    return res
}

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

时间空间复杂度都为n

[CoreJa]

思路

贪心法，从左到右+从右到左遍历，取最小值即可。

简单描述就是，从第一个c开始向右遍历数组，下标c的结果取0，后面的结果就分别递增直到再次遇到c置0。同样的过程从最后一个c开始向左遍历，第二次遍历的时候和第一遍遍历的结果比较，取最小值。

代码

class Solution:
    # 贪心解法
    def shortestToChar1(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [float('inf')] * n
        cnt = float('inf')
        for i in range(n):
            if s[i] == c:
                ans[i] = 0
                cnt = 0
            else:
                cnt += 1
                ans[i] = cnt
        cnt = float('inf')
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                cnt = 0
                continue
            else:
                cnt += 1
                ans[i] = min(cnt, ans[i])
        return ans
    # 贪心法简单写法
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [0 if ch == c else None for ch in s]

        for i in range(1, n):
            if ans[i] != 0 and ans[i - 1] is not None:
                ans[i] = ans[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ans[i] is None or ans[i] != 0 and ans[i + 1] + 1 < ans[i]:
                ans[i] = ans[i + 1] + 1
        return ans

[gentleman-goodman]

Day2_821_字符的最短距离

思路

* 思路 遍历字符串，找到目标字母，并用a数组记下位置 遍历字符串，
* 将当前位置与a数组的位置进行相减，取最小值，记住用绝对值。 C语言4ms通过。

class Solution {
        public List<Integer> addToArrayForm(int[] num, int k) {
            List<Integer> res = new ArrayList<>();
            int carry = 0;//进位
            int l1 = num.length - 1;//最右边的索引开始
            while (l1 >= 0 || k != 0) {
                int x = l1 < 0 ? 0 : num[l1];//最左边，也就是前面没有数了，就附上0
                int y = k == 0 ? 0 : k % 10;//取余->取出个位数   ////最左边，也就是前面没有数了，就附上0
                int sum = x + y + carry;
                carry = sum / 10;
                res.add(sum % 10);
                l1--;
                k = k / 10;
            }
            //最左边的carr可能还有，判断是不是0
            if (carry != 0) {
                res.add(carry);
            }
            Collections.reverse(res);
            return res;
        }
    }

复杂度分析

• 时间复杂度：O(n*m) n:s的长度 m:list的长度

  空间复杂度：O(n+m)

[spacker-343]

思路

第一眼感觉用双指针能做，找到第一个 c 字符出现位置和第二个 c 字符出现位置，然后分别求出到当前 i 的距离，再进行比较，如果没出现第二个 c 字符（也就是 right2 == s.length() ），那么就直接取第一个 c 字符到当前 i 的距离就好。

代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] res=new int[s.length()];
        int right=0;
        int right2=1;
        while(right<s.length() && s.charAt(right)!=c){
            right++;
        }
        while(right2<s.length()&&s.charAt(right2)!=c){
            right2++;
        }
        for(int i=0; i<res.length; i++){
            // 如果索引i大于第二个c字符所在位置则更新right和right2
            if(i>right2){
                if(right2!=s.length()){
                    right=right2;
                    right2=right+1;
                    while(right2<s.length()&&s.charAt(right2)!=c){
                        right2++;
                    }
                }
            }
            if(right2==s.length()){
                // 说明此时只有right指针在c字符上
                res[i]=Math.abs(right-i);
            }else{
                res[i]=Math.min(Math.abs(right-i), right2-i);
            }
        }
        return res;
    }
}

复杂度

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

[ghost]

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        left = [float('inf') for _ in range(len(s))]
        right = [float('inf') for _ in range(len(s))]

        cur_min = float('inf')
        for i in range(len(s)):
            if s[i] == c:
                left[i] = 0
                cur_min = 0
            else:
                cur_min += 1
                left[i] = cur_min

        cur_min = float('inf')
        for i in range(len(s)-1, -1, -1):
            if s[i] == c:
                right[i] = 0
                cur_min = 0
            else:
                cur_min += 1
                right[i] = cur_min

        result = [min(left[i], right[i]) for i in range(len(s))]

        return result

[chen445]

代码

class Solution: 
    def shortestToChar(self, s: str, c: str) -> List[int]:
        prev_position=float('-inf')
        result=[]
        for i in range(len(s)):
            if s[i] == c:
                prev_position = i
            result.append(i-prev_position)
        prev_position=float('inf')
        for i in range(len(s)-1,-1,-1):
            if s[i]==c:
                prev_position =i
            result[i]= min(result[i],prev_position-i)
        return result

复杂度

Time: O(n)

Space: O(n)

[KennethAlgol]

语言

java

class Solution {
    /*
    分析（非C字符的分类如下）：
    1.只有左边有C字符： sdafC...
    2.左右两边都有C字符：...CdsfsC...
    3.只有右边有C字符：...Cdsff
    (在后面可以用一句代码实现这三种情况)
    */
    public int[] shortestToChar(String S, char C) {

        int[] res = new int[S.length()];
        int cur = S.indexOf(C), pre = cur;
        for(int i = 0; i < S.length(); i++){
            if(S.charAt(i) == C){//其实就是每当遍历到C就更新cur和pre
                res[i] = 0;
                pre = i;
                cur = S.indexOf(C, i+1);//注意：这里如果当前是最后一个C时，此时cur为-1，这也保证了上面的情况3

            }else{
                res[i] = Math.min(Math.abs(pre - i), Math.abs(cur - i));//
            }
        }
        return res;
    }
}

[ZJP1483469269]

思路

记录下标index，以每个index为中心向周围增加给数组赋值，直到填满数组

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        index = [i for i,x in enumerate(s) if x == c]
        ls = [-1]*len(s)
        cnt = len(index)
        for i in index:
            ls[i] = 0
        step = 0
        while(cnt<len(s)):
            step = step + 1
            for i in index:
                for j in [-step,step]:
                    if i+j >= 0 and i+j < len(s) and ls[i+j] == -1:
                        ls[i+j] = step
                        cnt = cnt + 1
        return ls

复杂度分析

时间复杂度：O（n） 空间复杂度：O（n）

[suukii]

Link to LeetCode Problem

S1: 中心扩展法

这是最符合直觉的思路，对每个字符分别进行如下处理：

• 从当前下标出发，分别向左、右两个方向去寻找目标字符 C。
• 只在一个方向找到的话，直接计算字符距离。
• 两个方向都找到的话，取两个距离的最小值。

https://camo.githubusercontent.com/efaa1cd00bcef4ff7e2cf0c5cd7a37a60d403cf9f82439dffb63a1a48dcf3e06/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f3832315f302e706e67

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> res(S.length());

        for (int i = 0; i < S.length(); i++) {
            if (S[i] == C) continue;

            int left = i;
            int right = i;
            int dist = 0;

            while (left >= 0 || right <= S.length() - 1) {
                if (S[left] == C) {
                    dist = i - left;
                    break;
                }
                if (S[right] == C) {
                    dist = right - i;
                    break;
                }

                if (left > 0) left--;
                if (right < S.length() - 1) right++;
            }

            res[i] = dist;
        }

        return res;
    }
}

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  // 结果数组 res
  var res = Array(S.length).fill(0);

  for (let i = 0; i < S.length; i++) {
    // 如果当前是目标字符，就什么都不用做
    if (S[i] === C) continue;

    // 定义两个指针 l, r 分别向左、右两个方向寻找目标字符 C，取最短距离
    let l = i,
      r = i,
      shortest = Infinity;

    while (l >= 0) {
      if (S[l] === C) {
        shortest = Math.min(shortest, i - l);
        break;
      }
      l--;
    }

    while (r < S.length) {
      if (S[r] === C) {
        shortest = Math.min(shortest, r - i);
        break;
      }
      r++;
    }

    res[i] = shortest;
  }
  return res;
};

• Time: $O(N^2)$，N 为 S 的长度，两层循环。
• Space: $O(1)$

S2: 空间换时间

空间换时间是编程中很常见的一种 trade-off (反过来，时间换空间也是)。

• 因为目标字符 C 在 S 中的位置是不变的，所以我们可以提前将 C 的所有下标记录在一个数组 cIndices 中。
• 然后遍历字符串 S 中的每个字符，到 cIndices 中找到距离当前位置最近的下标，计算距离。

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();
        vector<int> c_indices;
        // Initialize a vector of size n with default value n.
        vector<int> res(n, n);

        for (int i = 0; i < n; i++) {
            if (S[i] == C) c_indices.push_back(i);
        }

        for (int i = 0; i < n; i++) {
            if (S[i] == C) {
                res[i] = 0;
                continue;
            }

            for (int j = 0; j < c_indices.size(); j++) {
                int dist = abs(c_indices[j] - i);
                if (dist > res[i]) break;
                res[i] = dist;
            }
        }

        return res;
    }
};

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  // 记录 C 字符在 S 字符串中出现的所有下标
  var cIndices = [];
  for (let i = 0; i < S.length; i++) {
    if (S[i] === C) cIndices.push(i);
  }

  // 结果数组 res
  var res = Array(S.length).fill(Infinity);

  for (let i = 0; i < S.length; i++) {
    // 目标字符，距离是 0
    if (S[i] === C) {
      res[i] = 0;
      continue;
    }

    // 非目标字符，到下标数组中找最近的下标
    for (const cIndex of cIndices) {
      const dist = Math.abs(cIndex - i);

      // 小小剪枝一下
      // 注：因为 cIndices 中的下标是递增的，后面的 dist 也会越来越大，可以排除
      if (dist >= res[i]) break;

      res[i] = dist;
    }
  }
  return res;
};

• Time: $O(NK)$，N 是 S 的长度，K 是字符 C 在字符串中出现的次数，K <= N*。
• Space: $O(K)$，K 为字符 C 出现的次数，这是记录字符 C 出现下标的辅助数组消耗的空间。

S3: 贪心

其实对于每个字符来说，它只关心离它最近的那个 C 字符，其他的它都不管。所以这里还可以用贪心的思路：

1. 先 从左往右 遍历字符串 S，用一个数组 left 记录每个字符 左侧 出现的最后一个 C 字符的下标；
2. 再 从右往左 遍历字符串 S，用一个数组 right 记录每个字符 右侧 出现的最后一个 C 字符的下标；
3. 然后同时遍历这两个数组，计算距离最小值。

优化 1

再多想一步，其实第二个数组并不需要。

因为对于左右两侧的 C 字符，我们也只关心其中距离更近的那一个，所以第二次遍历的时候可以看情况覆盖掉第一个数组的值：

1. 字符左侧没有出现过 C 字符
2. i - left > right - i (i 为当前字符下标，left 为字符左侧最近的 C 下标，right 为字符右侧最近的 C 下标)

如果出现以上两种情况，就可以进行覆盖，最后再遍历一次数组计算距离。

优化 2

如果我们是直接记录 C 与当前字符的距离，而不是记录 C 的下标，还可以省掉最后一次遍历计算距离的过程。

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();
        vector<int> dist(n, n);

        for (int i = 0; i < n; i++) {
            if (S[i] == C) dist[i] = 0;
            else if (i > 0) dist[i] = dist[i - 1] + 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            if (dist[i] == n
                || (i < n - 1 && dist[i + 1] + 1 < dist[i]))
                    dist[i] = dist[i + 1] + 1;
        }

        return dist;
    }
};

/**
 * 优化1：覆盖最近距离
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  var res = Array(S.length);

  // 第一次遍历：从左往右
  // 找到出现在左侧的 C 字符的最后下标
  for (let i = 0; i < S.length; i++) {
    if (S[i] === C) res[i] = i;
    // 如果左侧没有出现 C 字符的话，用 Infinity 进行标记
    else res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1];
  }

  // 第二次遍历：从右往左
  // 找出现在右侧的 C 字符的最后下标
  // 如果左侧没有出现过 C 字符，或者右侧出现的 C 字符距离更近，就更新 res[i]
  for (let i = S.length - 1; i >= 0; i--) {
    if (res[i] === Infinity || res[i + 1] - i < i - res[i]) res[i] = res[i + 1];
  }

  // 计算距离
  for (let i = 0; i < res.length; i++) {
    res[i] = Math.abs(res[i] - i);
  }
  return res;
};

/**
 * 优化2: 直接计算距离
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  var res = Array(S.length);

  for (let i = 0; i < S.length; i++) {
    if (S[i] === C) res[i] = 0;
    // 记录距离：res[i - 1] + 1
    else res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1] + 1;
  }

  for (let i = S.length - 1; i >= 0; i--) {
    // 更新距离：res[i + 1] + 1
    if (res[i] === Infinity || res[i + 1] + 1 < res[i]) res[i] = res[i + 1] + 1;
  }

  return res;
};

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        n = len(s)
        res = [0 if s[i] == c else None for i in range(n)]

        for i in range(1, n):
            if res[i] != 0 and res[i - 1] is not None:
                res[i] = res[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if res[i] is None or res[i + 1] + 1 < res[i]:
                res[i] = res[i + 1] + 1
        return res

• Time: $O(N)$，N 是 S 的长度。
• Space: $O(1)$

S4: 窗口

把 C 看成分界线，将 S 划分成一个个窗口。然后对每个窗口进行遍历，分别计算每个字符到窗口边界的距离最小值。

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();

        int l = S[0] == C ? 0 : n;
        int r = S.find(C, 1);

        vector<int> dist(n);

        for (int i = 0; i < n; i++) {
            dist[i] = min(abs(i - l), abs(r - i));
            if (i == r) {
                l = r;
                r = S.find(C, r + 1);
            }
        }

        return dist;
    }
};

/**
 * @param {string} S
 * @param {character} C
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
  // 窗口左边界，如果没有就初始化为 Infinity，初始化为 S.length 也可以
  let l = S[0] === C ? 0 : Infinity,
    // 窗口右边界
    r = S.indexOf(C, 1);

  const res = Array(S.length);

  for (let i = 0; i < S.length; i++) {
    // 计算字符到当前窗口左右边界的最小距离
    res[i] = Math.min(Math.abs(i - l), Math.abs(r - i));

    // 遍历完了当前窗口的字符后，将整个窗口右移
    if (i === r) {
      l = r;
      r = S.indexOf(C, l + 1);
    }
  }

  return res;
};

class Solution(object):
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """
        n = len(s)
        res = [0 for _ in range(n)]

        l = 0 if s[0] == c else n
        r = s.find(c, 1)

        for i in range(n):
            res[i] = min(abs(i - l), abs(r - i))
            if i == r:
                l = r
                r = s.find(c, l + 1)
        return res

• Time: $O(N)$，N 是 S 的长度。
• Space: $O(1)$

[Myleswork]

思路

遍历每一个字符，对当前字符设左右双指针，返回较近c和当前字符距离。 有一点需要注意，可能左指针或右指针在向左向右遍历时，会遍历到字符头和尾，此时就需要处理距离异常的问题。通过下面这行代码就能确保得到最短且正确（某一指针遍历到边界但另一指针仍在找c这一情况）的距离：

res.push_back(max(abs(i-left),abs(i-right)));

代码

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int len = s.length();
        vector<int> res;
        for(int i = 0;i<len;i++){
            int left = i;
            int right = i;
            while(s[left]!=c && s[right]!=c){
                if(left>0) left--;
                if(right<len) right++;
            }
            res.push_back(max(abs(i-left),abs(i-right)));
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n^2) 空间复杂度：O(n)

[Toms-BigData]

【Day 2】821. 字符的最短距离

思路

建立距离数组，找到首位和末位的字符，将距离数组首位字符之前和末位字符后的字符距离更新，之后将两字符之间的字母前向遍历一次，后向遍历一次，更新距离数组，返回距离数组

代码

func shortestToChar(s string, c byte) []int {
    first_num := strings.IndexByte(s, c)
    last_num := strings.LastIndexByte(s, c)
    array := make([]int, len(s))
    if first_num == last_num {
        for i := 0; i < len(s); i++ {
            array[i] = int(math.Abs(float64(i - first_num)))
        }
        return array
    }

    for k, _ := range s[:first_num] {
        array[k] = int(math.Abs(float64(k - first_num)))
    }
    if last_num < len(s)-1 {
        for i := last_num;i<len(s);i++{
            array[i] = int(math.Abs(float64(i - last_num)))
        }
    }
    if first_num + 1 < last_num{
        period_num := first_num
        for i := first_num; i < last_num; i++ {

            if s[i] == c {
                period_num = i
            }
            array[i] = int(math.Abs(float64(i - period_num)))
        }
        period_num = last_num
        for i := last_num; i > first_num; i-- {
            if s[i] == c {
                period_num = i
            }
            array[i] = int(math.Min(math.Abs(float64(i-period_num)), float64(array[i])))
        }
    }
    return array
}

复杂度

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

[shamworld]

var shortestToChar = function(s, c) {
    let arr = [];
    let result = [];
    for(let i = 0;i < s.length; i++){  
        if(s[i]===c){
            arr.push(i)
        }
    }
    for(let i = 0;i < s.length; i++){
        if(s[i]===c){
            result[i] = 0;
            continue
        }

        for(let index of arr){
            let res = Math.abs(index-i);
            console.log(result)
            if(res>=result[i]) break;
            result[i] = res;
        }
    }
    return result
};

[devosend]

思路

正反两次遍历，取较小的值存储到列表中返回。

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        result = []
        min = -float('inf')
        for i in range(len(s)):
            if s[i] == c:
                min = i
            result.append(i - min)

        max = float('inf')
        for i in range(len(s) - 1, -1, -1):
            if s[i] == c:
                max = i
            result[i] = result[i] if result[i] < max - i else max - i

        return result

复杂度分析

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

[tongxw]

思路

正序遍历和逆序遍历，取最小值

代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];

        int count = n + 1;
        for (int i=0; i<n; i++) {
            char cur = s.charAt(i);
            count = cur == c ? 0 : count + 1;
            ans[i] = count;
        }

        for (int i=n-1; i>=0; i--) {
            char cur = s.charAt(i);
            count = cur == c ? 0 : count + 1;
            ans[i] = Math.min(ans[i], count);
        }

        return ans;
    }
}

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

[pangjiadai]

思路

1. 暴力记录每一个c的index，然后遍历找到最小值，时间复杂度O(nm)
2. 遍历两次：从左到右，从右到左，记录最小值，时间复杂度O(m)

Python3

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

        # for index, char in enumerate(s):
        #     min_distance = len(s)
        #     for i in index_list:
        #         distance = abs(i-index)
        #         if distance < min_distance:
        #             min_distance = distance
        #     ans[index] = min_distance

        # return ans

        ans = [len(s)] * len(s)
        index = -1

        # from left to right
        for i in range(len(s)):
            if s[i] == c:
                index = i
            if index == -1:
                continue
            ans[i] = abs(i - index)

        # from right to left
        index2 = len(s)
        for j in range(len(s)-1, -1, -1):
            if s[j] == c:
                index2 = j
            if index2 == len(s):
                continue
            ans[j] = min(ans[j], abs(j-index2))

        return ans

[HondryTravis]

思路

遍历每一个字符，对当前字符设左右双指针，返回较近c和当前字符距离。

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function (S, C) {
    const result = []

    //  先找到前两个出现的位置
    for (let i = 0, l = S.indexOf(C), r = S.indexOf(C, l + 1); i < S.length; i++) {
        // 计算与左指针的距离
        result[i] = Math.abs(l - i)
        if (r === -1) continue

        // 如果右指针存在,取较小的距离
        result[i] = Math.min(result[i], r - i)

        // 走到右指针则左右指针往下一个
        if (i != r ) continue

        result[i] = 0
        l = r
        r = S.indexOf(C, r + 1)
    }
    return result
};

复杂度分析

时间复杂度 O(n)

空间复杂度 O(1)

[Flower-F]

解题思路

使用双指针，因为对于一个点来说，影响距离的字符 c 最多只有两个（当两个 c 在该点的不同方向）。 具体思路见代码注释。

代码

function shortestToChar(s: string, c: string): number[] {
    const arr: number[] = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            arr.push(i); // 存储所有的字符 c 位置
        }
    }

    const res: number[] = [];
    let cur = 0; // 当前选择的下标
    let index1, index2; // 双指针
    if (arr.length === 1) {
        index1 = index2 = arr[0];
    } else {
        index1 = arr[cur], index2 = arr[++cur];
    }

    for (let i = 0; i < s.length; i++) {
        // 当超越了 index2 指针的时候，就需要交换指针了
        // 此处需要考虑数组边界
        if (i > index2 && cur + 1 <= arr.length - 1) {
            index1 = index2;
            index2 = arr[++cur];
        }

        const dist1 = Math.abs(index1 - i);
        const dist2 = Math.abs(index2 - i);
        res.push(Math.min(dist1, dist2));
    }

    return res;
};

复杂度

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