【Day 2 】2022-04-02 - 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 中的所有字母均为小写字母。

[ha0cheng]

思路： 遍历两遍，第一遍确定字符的位置，第二遍确定距离每个字符位置最近的字符区间，输出结果

代码：

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        P = []
        for i in range(len(s)):
            if s[i] == c:
              P.append(i)
        r = []
        left = 0
        for i in range(len(P)):
            if i==len(P)-1:
                right = len(s)-1
            else:
                right = (P[i]+P[i+1]-1)//2
            j = P[i] - left 
            while j>0:
                r.append(j)
                j-=1
            while j<=right-P[i]:
                r.append(j)
                j+=1

            left = right+1

        return r

时间复杂度：需要遍历两遍，每次均是原字符数组的长度，所以复杂度为O(N) 空间复杂度：需要一个空间来存储字符位置，最坏情况下是N，复杂度为O(N)

[nancychien]

思路：

1. 找出目標 index 位置並 save to a target list

2. loop through 原來的字串和target list 並計算最小距離 ` class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: target = [] output = []

   for i in range(len(s)):
       if s[i] == c:
           target.append(i)
   
   for i in range(len(s)):
       output.append(min(abs(i-x) for x in target))
   
   return output

   `

Time complexity: O(n^2) Space complexity:O(n)

[shawnhu23]

Idea

Iterate through the string for 3 times. Locate all occurrences of c in the first iteration. Update distance based on distance on the left side in the second iteration and update distance based on distance on the right side in the third iteration.

Code

class Solution {
    public int[] shortestToChar(String s, char c) {
        char[] str = s.toCharArray();
        int[] ans = new int[str.length];
        Arrays.fill(ans, Integer.MAX_VALUE);
        for (int i = 0; i < str.length; i++) {
            if (str[i] == c) {
                ans[i] = 0;
            }
        }

        for (int i = 0; i < str.length - 1; i++) {
            if (ans[i] != Integer.MAX_VALUE) {
                ans[i+1] = Math.min(ans[i] + 1, ans[i+1]);
            }
        }

        for (int i = str.length-1; i > 0; i--) {
            if (ans[i] != Integer.MAX_VALUE) {
                ans[i-1] = Math.min(ans[i] + 1, ans[i-1]);
            }
        }
        return ans;
    }
}

Complexity

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

[LannyX]

代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] res = new int[s.length()]; //create new array to store answer
        int dummy = Integer.MIN_VALUE/2; // initiate a variable as the min value to store 

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == c) dummy = i;
            res[i] = i - dummy;
        }

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

    }
}

[Davont]

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    const sArr = s.split('');
    const keyArr = [];
    const ans = [];
    for (let i = 0; i < sArr.length; i++) {
        const ele = sArr[i];
        if(ele === c){
            keyArr.push(i);
        }
    }
    for (let i = 0; i < sArr.length; i++) {
        const ele = sArr[i];
        let minLen = sArr.length;
        for (let j = 0; j < keyArr.length; j++) {
            const keyEle = keyArr[j];
            minLen = Math.min(minLen,Math.abs(keyEle - i));
        }
        ans.push(minLen);
    }
    return ans;

};

[freedom0123]

原题链接

算法一

1. 时间复杂度为：O(n ^ 2)
2. 思路：暴力枚举，对于每个位置都向左右两个方向进行搜索，判断每个位置上的字符是否是c，如果是，进行相应的计算即可

   class Solution {
   public int[] shortestToChar(String s, char c) {
   int n = s.length();
   int[] ans = new int[n];
   for(int i = 0; i < n; i++){
   int left = i;
   int right = i+1;
   int res  = Integer.MAX_VALUE;
   while(left >= 0) {
   if(s.charAt(left) == c) res = Math.min(res, Math.abs(i - left));
   left --;
   }
   while(right < n) {
   if(s.charAt(right) == c) res = Math.min(res, Math.abs(i - right));
   right ++;
   }
   ans[i] = res;
   }
   return ans;
   }
   }

   算法二

• 时间复杂度：O(n)
  • 思路： 在算法一中，对于每个位置我们都要向左 和向右搜索距离这个位置最近的c，这种算法的时间复杂度很高，并且在做很多无用功。对于每个位置，我们如果说知道了他的前一位，距离最近的c 的位置，我们就不需要每个位置都进行枚举
  • 通过这种思想，我们只需要向左扫一遍，记住每个位置上，左边距离它最近的c的距离；在向右扫一遍，记住每个位置上，右边距离它最近的c的位置，就行。
  • 这里pre 除以2 的目的是为了，防止越界

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        int pre = Integer.MIN_VALUE / 2;
        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == c) {
                pre = i;
            }
            ans[i] = i - pre;
        }
        pre = Integer.MAX_VALUE / 2;
        for(int i = n -1; i >= 0; i--) {
            if(s.charAt(i) == c) {
                pre = i;
            }
            ans[i] = Math.min(ans[i],pre- i);
        }
        return ans;

    }
}

[suukii]

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* shortestToChar(char * s, char c, int* returnSize) {
    int len = strlen(s);
    int* res = malloc(sizeof(int) * len);

    res[0] = s[0] == c ? 0 : len;

    for (int i = 1; i < len; ++i)
        res[i] = s[i] == c ? 0 : res[i - 1] + 1;

    for (int i = len - 2; i >= 0; --i)
        res[i] = fmin(res[i], res[i + 1] + 1);

    *returnSize = len;
    return res;
}

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

[flaming-cl]

821. Shortest Distance to a Character

     1. 思路

     • 基础思路
     • 求数组中两个元素 i, j 的距离: i - j
     • 拓展
     • 求 i 到左右两边 j、h 的最短距离

       2. 细节

     • j 的位置未知：
     • 开一个线性数据结构，记录 j 的位置
     • 离 i 最近的元素不一定是 j，i 可能还有左相邻、且距离更近的元素 h：
     • 求最短距离时，比较 Math.min(Math.abs(i - j), Math.abs(i - h))
     • i - j、i - h，索引不应越界

       3. 复杂度

     • 时间：O(n)
     • 遍历 s，且遍历内部无 O(n) 及以上层级的操作
     • 空间：O(n)
     • 新开了 resultArr 数组

var shortestToChar = function(s, c) {
  const cHash = new Array(s.length).fill(0);
  let cHashStart = 0;
  const resultArr = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === c) {
      cHash[cHashStart] = i;
      cHashStart++;
      resultArr[i] = 0;
    }
  }
  cHashStart = 0;
  cHashPrev = 0;
  for (let i = 0; i < s.length; i++) {
    if (i !== cHash[cHashStart]) {
      cHashPrev = cHashStart > 0 ? cHashStart - 1 : 0;
      const shortestGap = Math.min(
        Math.abs(cHash[cHashPrev] - i),
        Math.abs(cHash[cHashStart] - i)
      );
      resultArr[i] = shortestGap;
    } else {
      cHashStart++;
    }
  }
  return resultArr;
};

[pureryuDo]

思路

进行两次遍历

使用prev记录上一次出现的c的位置，初始值设为极小的负数。

第一次从左到右遍历，记录当前位置i到prev的绝对值。

第二次从右到左遍历，记录当前位置i到prev的绝对值，并与第一次遍历的结果取min存入结果数组，

代码

public int[] shortestToChar(String s, char c) {
    int[] result = new int[s.length()];
    char[] chars = s.toCharArray();
    /*记录当前遍历中上一个c出现的位置
        初始值设置为极小的负数用于在比较时获得正确的值*/
    int prev = Integer.MIN_VALUE/2;
    /*第一次遍历 从左到右 记录与上一个c的距离*/
    for (int i = 0; i < chars.length; i++){
        //还没有出现过c
        if (chars[i] == c){
            prev = i;
        }
        result[i] = Math.abs(i-prev);
    }
    /*第二次遍历 从右到左 记录与上一个c的距离*/
    prev = -1;
    for (int i = chars.length-1; i >= 0; i--){
        if (chars[i] == c){
            prev = i;
        }
        result[i] = Math.min(result[i],Math.abs(prev-i));
    }
    return result;
}

复杂度分析

时间复杂度：O(N) N为数组长度

额外空间复杂度：O(N) 新建了一个长度为N的数组用于存放结果

[houmk1212]

思路

因为是找左右侧距离目标字符的最短距离，想到类似单调栈的找右侧最小或者最大值的做法。左侧的目标字符的下表可以用一个变量存，右侧的目标距离可以用单调栈来得到。当目标元素入栈时，弹出所有栈中非目标字符，并得到他们的结果。

代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[s.length()];
        int pre = - 1;
        for (int i = 0 ; i < s.length(); i ++) {
            if (s.charAt(i) == c) {
                while (!stack.isEmpty() && s.charAt(stack.peek()) != c) {
                    int p = stack.pop();
                    ans[p] = pre >= 0 ? Math.min(Math.abs(p - i) , Math.abs(p - pre)) : Math.abs(p - i);
                }
                pre = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int p = stack.pop();
            ans[p] = s.charAt(p) == c ? 0 : Math.abs(p - pre);
        }
        return ans;
    }
}

复杂度

时间复杂度： 每个字符串s中的字符都要入栈一次，出栈一次，所以时间复杂度是O（N）， N是字符串的长度。 空间复杂度：栈的大小，是O（N）。

[ShawYuan97]

题目地址(821. 字符的最短距离)

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

题目描述

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

 

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

示例 2：

输入：s = "aaab", c = "b"
输出：[3,2,1,0]

 

提示：
1 <= s.length <= 104
s[i] 和 c 均为小写英文字母
题目数据保证 c 在 s 中至少出现一次

前置知识

窗口的左右边界

公司

• 暂无

思路

将字符c作为窗口的边界 每次记录窗口的左右边界 然后开始计算距离

关键点

• 如何确定第一个窗口？\ 由于第一个窗口可能不存在左边界，因此先从索引位置0开始判断左边界是否存在，如果不存在可以将左边界置为n，那么第一个窗口可以不考虑左边界
• 如何更换窗口？\ 随着对字符串的遍历，一定会遍历到窗口右边界，那么新窗口的左边界就是当前索引i
• 如何使用字符串查找函数？ \ s.find(c,beg=i,end=n)，该函数会从字符串s中查找字符c，然后beg表示开始的索引，end表示结束的索引（左闭右开）；如果找不到返回-1

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        """寻找距离最近的字符的长度 

        Args:
            s(str):字符串
            c(str):字符

        Returns:
            ans(List[int]):返回结果列表

        """
        n = len(s)
        ans = [0] * n

        # 寻找左边界 如果没有左边界 那么直接将左边界设置为字符串长度
        l = 0 if s[0] == c else n
        # 从索引位置1开始搜索字符c
        r = s.find(c,1) 

        for i in range(n):
            # 取距离两个边界的最小距离
            ans[i] = min(abs(i-l),abs(r-i))
            # 考虑移动边界的问题
            if i == r:
                l = i
                r = s.find(c,i+1)
        return ans

复杂度分析

令 n 为数组长度。

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

[mo660]

思路

先从左向右遍历，再从右向左遍历取最小值

代码

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> answer(s.size());
        int pre = INT32_MIN/2;
        for (int i = 0; i < s.size() ; i++){
            if (s[i] == c) pre = i;
            answer[i] = i - pre;
        }
        pre = INT32_MAX;
        for (int i = s.size()-1 ; i >= 0 ; i--){
            if (s[i] == c) pre = i;
            if (answer[i] > (pre - i))
                answer[i] = pre - i;
        }
        return answer;
    }
};

复杂度

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

[yz3516]

思路

先从左边往右扫，记录每个字符离C的距离； 然后从右边往左扫，如果比第一次扫的距离小则替换掉，这样最后剩下的就是每个字符距离C最短的距离；

代码

        int[] result = new int[S.length()];
        int currDist = S.length(); 
        for (int i = 0; i < S.length(); ++i) {
            currDist = S.charAt(i) == C ? 0 : currDist + 1;
            result[i] = currDist;
        }

        currDist = S.length();
        for (int i = S.length() - 1; i >= 0; --i) {
            currDist = S.charAt(i) == C ? 0 : currDist + 1;
            result[i] = Math.min(result[i], currDist);
        }
        return result;
    }

复杂度分析

• 时间复杂度：O(N)， N 为数组长度;
• 空间复杂度：O(N)，创建了新的array result;

[rzhao010]

Thoughts

1. Get all indices of c, go through s to compare i with indices of c
2. Traverse s from left side and right 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;
    }

Time Complexity

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

[TimmmYang]

思路

正反两次遍历，分别记录当前字符是c的index，初始值使用inf。第二次遍历时比较存入最小值。

代码

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

复杂度

时间复杂度：O(n)，n为s长度

空间复杂度：O(1)

[taojin1992]

Plan & Complexity:

It is guaranteed that c occurs at least once in s.
1 <= s.length <= 10^4

s = "loveleetcode", c = "e"

l o v e l e e t c o d e
m m m 0 1 0 0 1 2 3 4 0
3 2 1 0 1 0 0 1 2 2 1 0

idea: two traversals, left-> right, right -> left

Time: O(s.length())
Space: O(s.length()) for the distances array

Code:

class Solution {
    public int[] shortestToChar(String s, char c) {
        int[] distances = new int[s.length()];
        int toCompare = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                distances[i] = 0;
                toCompare = i;
            } else {
                distances[i] = Math.abs(toCompare - i);
            }
        }

        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                distances[i] = 0;
                toCompare = i;
            } else {
                distances[i] = Math.min(distances[i], Math.abs(toCompare - i));
            }
        }

        return distances;
    }
}

[caterpillar-0]

思路

两次遍历，从左到右更新一遍，从右到左更新一遍

代码

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int>res(s.size());
        //方法二，只遍历两次，先从左到右，再从右到左
        int prev=INT_MAX/2;//防止越界，所以除以2
        for(int i=0;i<s.size();i++){
            if(s[i]==c){
                prev=i;
            }
            res[i]=i-prev;
        }
        prev=INT_MAX/2;
        for(int i=s.size()-1;i>=0;i--){
            if(s[i]==c){
                prev=i;
            }
            res[i]=min(abs(res[i]),prev-i);
        }
    return res;
    }
};

复杂度分析

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

[Zhen-Guan]

思路

先正序遍历 再倒着遍历一遍

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        res = []
        idx = -float("inf")
        for i in range(len(s)):
            if s[i] == c:
                idx = i 
            # i - 负无穷 = 正无穷
            res.append(i - idx)
        idx = float("inf")
        for i in range(len(s) - 1, -1 , -1):
            if s[i] == c:
                idx = i 
            res[i] = min(idx - i, res[i])
        return res

时间复杂度

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

[linjunhe]

思路

暴力解法，遍历找到index；将answer里的值设置很大，循环range(0, len(s))+循环index，作差求绝对值，跟answer[i]比较大小

代码 （python3）

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        index = [i for i,si in enumerate(s) if si==c]
        answer = [len(s)]*len(s)
        for i in range(0, len(s)):
            for j in index:
                if abs(i-j)<answer[i]:
                    answer[i] = abs(i-j) 
        return answer

复杂度分析

• 时间复杂度： O(n^2)， n为s长度, 套了两个循环
• 空间复杂度： O(n)，n为answer数组长度

[xil324]

class Solution(object):
    #数组的遍历(正向遍历和反向遍历)
    #思路： 遍历两次，每次遍历，更新target到i的距离， 取两次遍历的最小值，也就是查看，左右target哪一个离i更近，更新result（返回数组）
    #result[target] = 0
    def shortestToChar(self, s, c):
        """
        :type s: str
        :type c: str
        :rtype: List[int]
        """

        result = [float('inf')] * len(s); 
        target = -len(s);
        for i in range(len(s)):
            if s[i] == c:
                target = i; 
            result[i] = min(result[i], abs(target-i)); 
        for i in range(len(s)-1, -1,-1):
            if s[i] == c:
                target = i; 
            result[i] = min(result[i], abs(target-i));
        return result;

时间复杂度： o(n) 空间复杂度： o(n)

[YuyingLiu2021]

两种方法

暴力
把s中和c相等的index取出来 之后一个个和s中的index相减 max(abs(差))
时间复杂度：O(N)
空间复杂度：O(N)

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

一个指针
当满足两个条件p+=1
1. p还没有走完
2. i 到  p 的绝对距离 > 到p + 1的绝对距离
时间复杂度：O(N)
空间复杂度：O(1)

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        res = []
        p = 0
        lst = list(i for i in range(len(s)) if s[i] == c)

        for i, j in enumerate(s):
            if p < len(lst) -1 and abs(lst[p] -i) > abs((lst[p+1]) -i):
                p+=1
            res.append(abs(lst[p]-i))

        return res

[LyuliangLiu]

Idea

• Go forward: record the distance between each letter and the latest c in its left;
• Go backward: update the distance if a letter is closer to the latest c in its right

  Code

  class Solution {
  public int[] shortestToChar(String s, char c) {
      int[] ans = new int[s.length()];
      int lastIndexC = Integer.MAX_VALUE;
      for (int i = 0; i < s.length(); i++) {
          if (s.charAt(i) == c) {
              ans[i] = 0;
              lastIndexC = i;
          } else if (lastIndexC == Integer.MAX_VALUE) {
              ans[i] = Integer.MAX_VALUE;
          } else {
              ans[i] = i - lastIndexC;
          }
      }
      lastIndexC = Integer.MAX_VALUE;
      for (int i = s.length() - 1; i >= 0; i--) {
          if (s.charAt(i) == c) {
              lastIndexC = i;
          } else if (lastIndexC - i < ans[i]) {
              ans[i] = lastIndexC - i;
          }
      }
      return ans;
  }
  }

  Complexity

• Time: 2N
• Space: N

[wychmod]

思路

（比较暴力）先把所有的e找出来下标放入数组中，然后将原数组的每一个点与所有e的下标对比取最小的那个。

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        el = []
        for i, n in enumerate(s):
            if n == c:
                el.append(i)
        res = [0]*len(s)
        for i in range(len(s)):
            less = abs(i-el[0])
            for j in el:
                less = min(abs(i-j), less)
            res[i] = less
        return res

复杂度分析

时间复杂度：O(n*目标字符在数组中出现的次数)

空间复杂度：O(n)

[zjsuper]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        dic = []
        for i,j in enumerate(s):
            if j == c:
                dic.append(i)
        ans = []

        for i in range(len(s)):
            temp = []
            for j in dic:
                temp.append(abs(j-i))
            ans.append(min(temp))
        return ans

[yinhaoti]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        """
        Brute-force
        TC: O(n^2)
        SC: O(n)
        """
        re = [-1] * len(s)

        for i in range(len(s)):
            shortest = float('inf')
            count = 0
            for j in range(i, -1, -1):
                if s[j] != c:
                    count += 1
                if s[j] == c:
                    shortest = min(shortest, count)

            count = 0
            for k in range(i, len(s)):
                if s[k] != c:
                    count += 1
                if s[k] == c:
                    shortest = min(shortest, count)
            re[i] = shortest

        return re

    def shortestToChar(self, s: str, c: str) -> List[int]:
        """
        Topic: Array enumerate
        Idea: enumerate 3times
            [-1] * n
            1st: put 0
            2nd: left->right, 0+1
            3rd: right->left, 0+1

        TC: O(n)
        SC: O(n)
        """
        l = len(s)
        re = [-1] * l

        for i in range(l):
            if s[i] == c:
                re[i] = 0

        cur_d = -1
        for i in range(l):
            print(re[i], cur_d)

            if re[i] == 0:
                cur_d = 0
            re[i] = cur_d
            if cur_d != -1:
                cur_d += 1

        # reversed enumerate
        cur_d = float('inf')
        for i in range(l-1, -1, -1):
            if re[i] == 0:
                cur_d = 0

            if cur_d < re[i] or re[i] == -1:
                re[i] = cur_d
            if cur_d != -1:
                cur_d += 1

        return re

[Magua-hub]

思路 分析一下可知，只有两种情况，即c在这个数的左边或者右边，所以我们遍历两次，一次从前向后，一次从后向前，最后把两次遍历的结果取min

代码

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        vector<int> res(n, INT_MAX);
        for(int i = 0, j = -1; i < n;  i ++){
            if(s[i] == c) j = i;
            if(j != -1) res[i] = i - j;
        }
        for(int i = n , j = -1; i >= 0; i --) {
            if(s[i] == c) j = i;
            if(j != -1) res[i] = min(res[i], j - i);
        }
        return res;

    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)结果数组

[xixiao51]

 思路

前序遍历数组找出与左侧的字母的最短距离，后序遍历数组找出与右侧字母的最短距离，两者取其最小为最终结果。

 代码

class Solution {
    public int[] shortestToChar(String s, char c) {
        int len = s.length();
        int[] result = new int[len];
        int max = len - 1;

        int cur = max;
        for(int i = 0; i < len; i++) {
            if (s.charAt(i) == c) {
                result[i] = 0;
                cur = 0;
            } else {
                result[i] = Math.min(max, ++cur);
            }
        }

        cur = max;
        for(int i = len - 1; i >= 0 ; i--) {
            if (s.charAt(i) == c) {
                cur = 0;
            } else {
                result[i] = Math.min(result[i], ++cur);
            }
        }

        return result;
    }
}

复杂度分析 - 时间复杂度：O(N)，其中 N 为String的长度。 - 空间复杂度：O(N), 其中 N 为String的长度。

[xiayuhui231]

题目

字符的最短距离 https://leetcode-cn.com/problems/shortest-distance-to-a-character/

思路

• 前后各遍历一次，找最短距离

  代码

  public:
  vector<int> shortestToChar(string s, char c) {
          vector<int> pos(s.size(),-1);
      int pre = -1;
      for(int i = s.size() -1;i >= 0;i--)
          if(s[i] == c){
              pre = i;
              pos[i] = 0;
          }else if(pre != -1) pos[i] = pre - i;
      pre = -1;
      for(int i = 0;i < s.size();i++){
          if(s[i] == c){
              pre = i;
      }else if(pos[i] == -1 && pre != -1){
          pos[i] = i - pre;
      }else if(pos[i] != -1 && pre != -1){
          pos[i] = min( i - pre, pos[i]);
      }
      }
      return pos;
  }
  };

  复杂度

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

[bigboom666]

思路

同时正向和反向遍历

code

class Solution {
    //同时正向和反向遍历
    public int[] shortestToChar(String s, char c) {
        int[] result = new int[s.length()];
        for(int i=0;i<s.length();i++){
            int head = i;
            int tail = i;
            while(true){
                if(head>=0 && s.charAt(head) == c) break;
                if(tail<s.length() && s.charAt(tail) == c) break;
                head--;
                tail++;
            }
            result[i] = (i-head)<(tail-i)?(i-head):(tail-i);
        }
        return result; 

    }
}

复杂度

时间：o(n^2) 空间：o(1)

[XiaoLiz]

思路:

先查遍历找出C值对应的下标索引存储includesIndex中， 在进行一次循环 当前值等于C那么距离直接为0，内部进行二次循环 includesIndex arr 进行绝对值计算

代码

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

    var res = Array(s.length).fill(0);
    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            res[i] = 0;
            continue;
        }

        for(let val of includesIndex ) {
            const dist = Math.abs(val - i)

            if (dist >= res[i]) break;
            res[i] = dist;
        }
    }
    return res;
};

复杂度分析

• 时间复杂度：O(N*K)，N 是 S 的长度，K 是字符 C 在字符串中出现的次数 K<=N
• 空间复杂度：O(K)，K 为字符 C 出现的次数

[wenliangchen]

思路：

先从左边遍历，每次遍历中 先找到对应的目标的下标，在过程中利用i的下标去减去最小值的二分之一，（目的是在没找到的情况下，通过减去最小值留下一个最大数值，最小值为负数 i - -则变为加法）。之后进行右边遍历，同理，在过程中进行大小的比较。对比两次遍历最小的值是哪个，这样即可得到正确答案。

用最小值的目的是为了避免溢出

class Solution {
    public int[] shortestToChar(String S, char C) {
        int len = S.length();
        int[] ans = new int[len];
        int prev = Integer.MIN_VALUE / 2;

        for (int i = 0; i < len; i++) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = i - prev;
        }

        prev = Integer.MAX_VALUE / 2;
        for (int i = len-1; i >= 0; i--) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }
}

复杂度分析

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

[zywang0]

class Solution {
    public int[] shortestToChar(String s, char c) {
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[s.length()];
        int pre = - 1;
        for (int i = 0 ; i < s.length(); i ++) {
            if (s.charAt(i) == c) {
                while (!stack.isEmpty() && s.charAt(stack.peek()) != c) {
                    int p = stack.pop();
                    ans[p] = pre >= 0 ? Math.min(Math.abs(p - i) , Math.abs(p - pre)) : Math.abs(p - i);
                }
                pre = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int p = stack.pop();
            ans[p] = s.charAt(p) == c ? 0 : Math.abs(p - pre);
        }
        return ans;
    }
}

[VictorHuang99]

4.2算法题： Idea： 1.找到指定字符在目标字符串的下标并放进一个数组记录。 2.循环比较字符串中每个字符距离和指定字符的距离，记录下较小的一个，放入另一个数组。

Code：

var shortestToChar = function(s, c) { var nearstXb = []; var absDis = [];

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

for(var i=0;i<s.length;i++){
    var min2 = s.length;
    for(var j=0;j<nearstXb.length;j++){
        var min1 = Math.abs(i-nearstXb[j])
        if(min1<min2){
           min2 = min1;}
    }
    absDis.push(min2);
}

return absDis;

}

时间复杂度：O(N^2) 空间复杂度：（1）

[youxucoding]

4月2日

• 【day02】

821. 字符的最短距离

难度简单218

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

思路：

1. 暴力解法：得到所有目标字符的下标，遍历字符串一一比较，获得最近距离
2. 滑动窗口：按照目标字符重复出现的位置，将字符串划分为若干窗口，在窗口内就可以计算出当前下标与目标字符最近距离。

代码实现：

• 暴力解法：

class Solution {
    public int[] shortestToChar(String s, char c) {
        ArrayList<Integer> list = new ArrayList<>();
        int res[] = new int[s.length()];
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == c){
                list.add(i);
            }
        }
        for(int j = 0;j < s.length();j++){
            res[j] = Integer.MAX_VALUE;
            for(Integer i : list){
                res[j] = Math.min(res[j],Math.abs(j-i));
            } 
        }
        return res;
    }
}

• 滑动窗口：

class Solution {
    public int[] shortestToChar(String s, char c) {
        int cur = 0;
        int left = Integer.MAX_VALUE;
        int right = -1;
        int res[] = new int[s.length()];
        while(cur < s.length()){
            right++;
            while((s.charAt(right) == c || right == s.length() - 1)&&cur <= right){
               if((right == s.length() - 1) && (s.charAt(right) != c)){
                   res[cur] = Math.abs(cur - left);
                   cur++;
               }else{
                    res[cur] = Math.min(Math.abs(cur-left),Math.abs(cur-right));
                    if(cur == right){
                        left = cur;
                    }
                    cur++;
                }

            }

        }
        return res;
    }
}

复杂度分析：

• 暴力解法：
  • 时间复杂度：O(m*n)
  • 空间复杂度：O(n)
• 滑动窗口：
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

[ghost]

思路

• 第一遍：从左向右遍历
• 第二遍：从右向左遍历，同时取最小值

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        prev = float('-inf')
        ans = []
        # 第一遍 从左向右遍历
        for i, x in enumerate(s):
            if x == c:
                prev = i
            ans.append(i - 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

复杂度分析

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

[JudyZhou95]

class Solution:
    def shortestToChar(self, S, C):
        def letter_get(letter, dr):
            n = len(S)
            res, cur = [0]*n, -n
            for i in range(n)[::dr]:
                if S[i] == letter: cur = i
                res[i] = abs(i - cur)
            return res

        return [min(x,y) for x,y in zip(letter_get(C, 1), letter_get(C, -1))]

[FutureFields]

Idea: scan from left to right, and reverse

class Solution { public: vector shortestToChar(string s, char c) { vector answer(s.size()); int prev = -100000; for (int i = 0; i < s.size(); i++) { if (s[i] == c) { prev = i; } answer[i] = i - prev; } prev = 20000; for (int i = s.size() - 1; i >= 0; i--) { if (s[i] == c){ prev = i; } answer[i] = min(answer[i], prev - i); } return answer; } };

space O(N), time O(N)

[duke-github]

思路

正向循环 查找第一个c的下标=k作为标识,将0-k的下标重新赋值。对接下的数据以i-k作为结果
查找下一个c 再将k到（i+k）/2之间的数据倒序赋值 依次直到最后。
第一步需要判断如果0下标为k的时候 按照第二步的逻辑赋值

复杂度

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

 代码

public int[] shortestToChar(String s, char c) {
        int k = 0;
        int[] ans = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                for (int j = i; j > (i + k) >> 1 || k == 0 && j >= k && s.charAt(0) != c; j--) {
                    ans[j] = i - j;
                }
                k = i;
            }
            ans[i] = i - k;
        }
        return ans;
    }

[zzz607]

思路

第一想法是以当前字符为中心，然后向左右两边搜索，搜索到的第一个C即可得到当前字符到C的最小距离。 但是这样的算法复杂度是O(N^2)

第二想法是首先将C在S中的索引全部找出来，这样就可以用当前字符的索引直接减到C的索引，从而得到一个最小值 这样的算法复杂度就是O(N)。下面的代码是这个想法的实现。

后来又看了一下官方的题解，发现是遍历正、反二次就可以解决了。果然是我太菜了。。。。。。

代码

func shortestToChar(s string, c byte) []int {
    var cIdx []int
    var ret []int

    initCIdx := func() {
        for i := 0; i < len(s); i++ {
            if s[i] == c {
                cIdx = append(cIdx, i)
            }
        }
    }

    getDistance := func(idx int) int {
        min := math.MaxInt32
        for _, ii := range cIdx {
            tmp := int(math.Abs(float64(ii - idx)))
            if tmp < min {
                min = tmp
            }
        }
        return min
    }

    initCIdx()
    for i := 0; i < len(s); i++ {
        ret = append(ret, getDistance(i))
    }

    return ret
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)，最坏时，C和S的长度一样

[lskong]

class Solution { public: vector shortestToChar(string s, char c) { vector pos; vector res; for(int i = 0; i < s.size(); i++) { if(s[i] == c) { pos.push_back(i); } } for(int i = 0; i < s.size(); i++) { int tmp = 100000000000000; for(int j = 0; j < pos.size(); j++) { tmp =min(tmp, abs(i -pos[j])); } res.push_back(tmp); } return res; } };

[dzwhh]

思路

先把字符串中等于c字符的对应下标存到数组res中，作为对比项使用，同时设置指向c字符下标数组的指针p，然后在遍历字符串每个字符，把每个字符的下标数值与res的c字符下标相减，得到距离，每次只比较c字符下标当前值和后继值，如果发现当前值的差值比后继值的差值大，那就把p指针向后挪一位，因为这时候当前值不需要在以后的判断中使用，因为肯定比后面的c字符位置要远,同时把字符串当前字符位置和c字符下标数组对应位置的差异存到dist最终结果数组中

关键点

• 下标差值的比较
• 当前字符位置与c字符前后2个位置的距离比较，大的代表距离远，需要移动指针

代码

• js 版本

const shortestToChar = (s, c) => {
  let res = []; // c字符下标数组
  let p = 0; // 指向c字符下标数组的指针
  let dist = []; // 最终结果

  // 把字符串中等于c字符的对应下标存在res数组中
  for(let i = 0; i < s.length; i++) {
    if (s[i] ===  c)
      res.push(i)
  }

  // 遍历字符串字符，比较每个字符下标与对应c字符下标的差值
  for(let j = 0; j < s.length; j++) {
    // 数组元素和c下标数组前后两个值对比,如果前一个比较值比后一个比较值大，p指针向后挪一位
    if (p < res.length && Math.abs(j - res[p]) > Math.abs(j - res[p+1])) 
      p++; 
    dist.push(Math.abs(j - res[p]));
  }
  return dist;
};

复杂度分析

时间复杂度:O(m+n) 空间复杂度:O(n)

[winrunwang]

思路: 遍历一次，用2个临时变量存储指针信息。中间第二个for循环调整距离问题 public int[] shortestToChar(String s, char c) { int first = -1; int temp = -1; int n = s.length(); int[] res = new int[n]; for (int i = 0; i < n; i++) { char t = s.charAt(i); if(t == c){ res[i] = 0; if(first == -1){ first = i; } if(temp!= -1){ for (int j = temp; j < i; j++) { res[j] = Math.min(i-j,res[j]); } } temp = i; } if(first != -1){ res[i] = i-temp; } } for (int i = 0; i < first; i++) { res[i] = first - i; } return res; }

[biscuit279]

思路:笨蛋解法，第一次遍历找位置，第二次遍历求距离最小值

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        ans = []
        position = []
        for i,item in enumerate(s):
            if item == c:
                position.append(i)

        for i in range(len(s)):
            dis = []
            for p in position:
                dis.append(abs(i-p))
            ans.append(min(dis))
        return ans

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

[oneline-wsq]

思路

首先在s中找到所有等于c的索引；再从0开始循环，计算与索引集合相减绝对值最小的值。

代码

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

        ans=[]
        # 首先找出所有的c的索引
        tmp=[]
        k=0
        for i in s:
            if i==c:
                tmp.append(k)
            k+=1

        for i in range(len(s)):
            tmp2=[abs(j-i)for j in tmp]
            ans.append(min(tmp2))

        return ans

复杂度分析

时间复杂度：O(n*m)

空间复杂度：O(n)

[MoonLee001]

思路

两次遍历字符串，取最小值。

代码

var shortestToChar = function(S, C) {
  let n = S.length;
  let prev = -Infinity;
  let ans = [];
  for (let i = 0; i < n; i++) {
    if (S.charAt(i) == C) {
      prev = i;
    }
    ans[i] = i - prev;
  }

  prev = Infinity;
  for(let i = n - 1; i >= 0; i--) {
    if (S.charAt(i) == C) {
      prev = i;
    }
    ans[i] = Math.min(prev - i, ans[i]);
  }

  return ans;

}

复杂度分析

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

[m908]

思路

先保存目标字符出现的所有位置，逐个与字符串比对距离

代码

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> result(s.size());
        vector<int> targetChars;

        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == c)
                targetChars.push_back(i);
        }

        for(int i=0; i < result.size(); i++)
        {
            int minDistance = INT_MAX;
            for(int j=0; j < targetChars.size(); j++)
            {
                if(minDistance > abs(i - targetChars[j]))
                    minDistance = abs(i - targetChars[j]);
            }
            result[i] = minDistance;
        }
        return result;
    }
};

复杂度

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

[carterrr]

class Solution { public int[] shortestToChar(String s, char c) { char[] array = s.toCharArray(); int len = s.length(); int[] res = new int[len]; Arrays.fill(res, len); int idx_c = -1; for(int i = 0; i < len ; i++) { if(array[i] == c) { idx_c = i; res[i] = 0; continue; } if(idx_c != -1) { res[i] = i - idx_c; } } for(int i = len - 1; i >= 0 ; i--) { if(array[i] == c) { idx_c = i; continue; } if(idx_c > i) { res[i] = Math.min(res[i], idx_c - i); }

        }
        return res;
}

}

[Ellie-Wu05]

思路

先建造一个index list 存储target character相应的index

在用index list 里面的值分别减去字符串单个的index，取最小值

代码

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

        index = [i for i, j in enumerate(s) if j==c]

        result = []
        for i in range(len(s)):
            a=[]
            for ind in index:
                b = abs(ind - i)
                a.append(b)
            min_num = min(a)
            result.append(min_num)

        return result

复杂度分析

时间：最差On^2, 正常O(mn) m 为index list 长度(最差m=n) \ 空间： On, index list 的worst case, On, result index 也是On

[ethanwlx]

思路：先从左往右，找每个index离左边最近的距离，再从右边往左，最后取左右的最小值。 时间：O(n) 空间：O(n) class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: ans_l = [float(inf)] len(s) ans_r = [float(inf)] len(s) ans = [0] * len(s)

    for i in range(len(s)):
        if i == 0:
            if s[i] == c:
                ans_l[i] = 0   
        else:
            ans_l[i] = ans_l[i-1] + 1 if s[i] != c else 0

    for i in range(len(s) - 1, -1, -1):
        if i == len(s) - 1:
            if s[i] == c:
                ans_r[i] = 0          
            ans[i] = min(ans_l[i], ans_r[i])
        else:
            ans_r[i] = ans_r[i+1] + 1 if s[i] != c else 0
            ans[i] = min(ans_l[i], ans_r[i])
    return ans

[AstrKing]

思路

左右两次遍历，找出最小值即可

代码

class Solution {
    public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = Integer.MIN_VALUE / 2;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = i - prev;
        }

        prev = Integer.MAX_VALUE / 2;
        for (int i = N-1; i >= 0; --i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)