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

[for123s]

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

[hatoriMain]

解法思路1:

注意要点：

这题先指针从左扫到右，再从右扫到左，把初始index设成一个很大的负值（这里设了20000是因为长度最大值是10000）。这里不能设Integer.MIN_VALUE因为之后会overflow。

计算从左往右时每个字符到字符c的距离。遇到第一个之前距离都是非常大。

扫完以后再从右往左扫，比较这个新的距离跟原来的距离哪个更小，这里注意index要设成一个正的很大的数，因为这样遇到第一个c之前右边的结果产生的数都会非常大，通过和原来的res[i]比较能得到正确的值。

复杂度：

时间：$O(n)$

空间：$O(1)$

两个for循环所以是O(n),开的数组只用来返回结果所以是O(1)

第一次自己写的代码：

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

[Ryanbaiyansong]

双指针 + 前后缀分解

··· class Solution: def shortestToChar(self, s: str, t: str) -> List[int]: n = len(s) ans = [0] * n idx = -n for i, c in enumerate(s): if c == t: idx = i ans[i] = i - idx

    idx = 2 * n
    for i in range(n - 1, -1, -1):
        c = s[i]
        if c == t:
            idx = i 
        ans[i] = min(ans[i], idx - i)

    return ans

    l = 0 if s[0] == t else n 
    r = s.find(t, start=1)
    for i in range(n):
        ans[i] = min(i - l, r - i)
        if i == r:
            l = r 
            r = s.find(t, start = l + 1)

    return ans

···

[Yufanzh]

forward and backward array traverse

tc: o(n) since we traverse the array without nest

sc: o(n) for initialize ans array

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

traverse forward and backward to get two list, first the min value between those two list

    # correct way to initialize ans
    ans = [0 if s[i] == c else None for i in range(len(s))] # 0 means distance
    # forward scan
    for i in range(1, len(s)):
        if ans[i] != 0 and ans[i-1] is not None:
            ans[i] = ans[i-1] + 1
            # if i index is not c, and previous distance has value

    # backward scan
    for i in range(len(s)-2, -1, -1):
        if ans[i] is None or ans[i] > ans[i+1] + 1:
            ans[i] = ans[i+1] + 1 # not updated yet or value larger than backward scan
    return ans

[JiangyanLiNEU]

Idea

• use Two Pointers to decide which index is the cloest
• get all c's index in s

• iterate through s and get the smallest distance

  class Solution:
  def shortestToChar(self, s: str, c: str) -> List[int]:
      # Get all c's index in s
      c_index = []
      for index, value in enumerate(s):
          if value == c:
              c_index.append(index)
  
      ans = []
      cur = c_index.pop(0)
      for i in range(len(s)):
          distance_cur = cur-i if cur-i >= 0 else i-cur
          if not c_index:
              ans.append(distance_cur)
          else:
              distance_next = c_index[0]-i if c_index[0]-i>=0 else i-c_index[0]
              ans.append(min(distance_cur, distance_next))
              if distance_next <= distance_cur:
                  cur = c_index.pop(0)
      return ans

• Time Complexity = O(N) N= len(s)
• Space Complexity = O(N) N= len(s)

[yfu6]

class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: a,n=[],len(s) for i in range(n): if s[i]==c: a.append(i) answer=[] j=0 for i in range(n): if s[i]==c: answer.append(0) j+=1 elif i<a[0]: answer.append(a[0]-i) elif i>a[-1]: answer.append(i-a[-1]) else: answer.append(min((a[j]-i),(i-a[j-1]))) return answer

[kofzhang]

思路

1.先找到所有字符位置，添加到一个列表里 2.双指针，一个指向字符位置列表，一个指向原列表 3.如果位置列表存在下一个位置，并且下一个位置到当前字符位置的绝对值小于当前位置到当前字符位置的绝对值，字符位置列表索引+1，并计算位置。否则以当前字符位置直接计算距离。

复杂度

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

代码

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

[huifeng248]

思路： 左右指针算距离上一个的距离。然后比对两个array 的最小值

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

        # When going left to right, we'll remember the index prev of the last character C we've seen. Then the answer is i - prev.
        # When going right to left, we'll remember the index prev of the last character C we've seen. Then the answer is prev - i.
        # We take the minimum of these two answers to create our final answer.

        left_res = [None]*len(s)
        right_res = [None]*len(s)
        res = []

        prev = float('-inf')
        # check from left
        for i, char in enumerate(s):    
            if char == c:
                prev = i
            left_res[i] = i - prev

        # check from right
        right_prev = float('inf')
        for j in range(len(s)-1, -1, -1):
            right_res[j] = float('inf')
            if s[j] == c:
                right_prev = j
            right_res[j] = right_prev - j

        for i in range(len(s)):
            ele = min(left_res[i], right_res[i])
            res.append(ele)
        return res

# time complexity O(n)
# space complexity O(n)

[LIMBO42]

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> ans(s.length(), s.length());
        int pre = 2 * s.length();
        for(int i = 0; i < s.length(); ++i) {
            // 先记录离左边最近的
            if(s[i] == c) {
                pre = i;
            }
            ans[i] = min(abs(i - pre), ans[i]);
        }
        pre = 2 * s.length();
        for(int i = s.length()-1; i >=0; --i) {
            // 先记录离左边最近的
            if(s[i] == c) {
                pre = i;
            }
            ans[i] = min(abs(i - pre), ans[i]);
        }
        return ans;
    }
}c++;

[Size-of]

/**

• @param {string} s
• @param {character} c

• @return {number[]} */ var shortestToChar = function(s, c) { const res = new Array(s.length).fill(Infinity) for (let i = 0; i < s.length; i++) { res[i] = s.substr(i, 1) === c ? 0 : (res[i - 1] != undefined ? res[i - 1] : Infinity) + 1 }

  for (let i = s.length - 1; i >= 0; i--) { let prev = res[i + 1] !== undefined ? res[i + 1] : Infinity res[i] = prev + 1 < res[i] ? prev + 1 : res[i] }

  return res }; 时间复杂度O(n),空间复杂度O(1)

[duke-github]

思路

一次遍历 回头赋值

复杂度

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

代码

class Solution {
    public static int[] shortestToChar(String s, char c) {
        int index = s.length(), i = -1;
        int[] ans = new int[s.length()];
        for (char a : s.toCharArray()) {
            i++;
            if (a == c) {
                //当前下标的字母为标记字母
                ans[i] = 0;
                int k = i;
                index = i;
                //向前遍历 直到数组中某位的值＜当前位置和该值下标的差
                while (k >= 1 && ans[--k] > i - k) {
                    ans[k] = i - k;
                }
            }
            ans[i] = Math.abs(i - index);
        }
        return ans;
    }
}

[bookyue]

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

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

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

        return ans;
    }

[feefeefee]

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    let len = s.length
    const arr = Array(s.length)
    let l_current = null
    let r_current = null

    for(let i = 0; i < len ; i++){
        l_current = s[i] === c ? i :l_current
        arr[i] = l_current !== null ? Math.abs(i - l_current) : Infinity
    }

     for(let i = len-1; i >=0 ; i--){
        r_current = s[i] === c ? i : r_current
        if(r_current !== null){
            const abs = Math.abs(i -r_current)
            arr[i] = arr[i] < abs ? arr[i]:abs
        }
    }
    return arr
};

[NorthSeacoder]

思路

• 两次遍历
• j 用来保留上次字符出现的位置
• 从左往右获取左侧距离
• 从右往左获取右侧距离

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    const n = s.length;
    const res = new Array(n).fill(Infinity);
    for (let i = 0, j = -1; i < n; i++) {
        if (s.at(i) === c) j = i;
        if (j !== -1) res[i] = i - j;
    }
    for (let i = n - 1, j = -1; i >= 0; i--) {
        if (s.at(i) === c) j = i;
        if (j !== -1) res[i] = Math.min(res[i], j - i);
    }
    return res;
};

复杂度

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

[nikojxie]

思路

遍历每一个字符，再用两个指针同时遍历其左右的字符，找到就退出循环

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
  const answer = new Array(s.length)
  for(let index = 0; index < s.length; index ++) {
    const str = s[index]
    let left = index, right = index + 1
    while(left >= 0 || right < s.length) {
      if(s[left] === c) {
        answer[index] = index - left
        break
      }
      if(s[right] === c) {
        answer[index] = right - index
        break
      }
      left --
      right ++
    }
  }
  return answer
};

复杂度

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

[zcytm3000]

class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: a=[] b=[] for i,ch in enumerate(s): if ch==c: b.append(int(i)) return([min(abs(x-i) for i in b) for x in range(len(s))])

[Elsa-zhang]

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

        ans = []
        for i, w in enumerate(s):
            dis = [abs(p-i) for p in pos]
            ans.append(min(dis))
        return ans

[954545647]

思路

先记录 S 中存在字符 C 的位置，然后二次 for 循环去遍历

代码

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

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

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

    // 非目标字符，到下标数组中找最近的下标
    for (const cIndex of hasCArr) {
      const dist = Math.abs(cIndex - i);
      if (dist >= res[i]) break;
      res[i] = dist;
    }
  }
  return res;
};

[zzhilin]

思路

first pass left to right to calculate distance between last index of c (prev) and current index of element i, save answer to arr. second pass right to left to calculate distance between current i and last index of c. compare with saved answers to find minimum

代码

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

        prev = float('-inf')
        ans = []
        for i, ele in enumerate(s):
            if ele == 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(prev - i, ans[i])

        return ans

复杂度分析 时间: O(n) all elements in s 空间: O(n) ans array

[hjy-u]

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

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

[csthaha]

思路：

• 获取字符c在s中的所有索引列表
• getDistance 获取字符在索引列表中的最小值。

  复杂度：

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

  代码：

  /**
  * @param {string} s
  * @param {character} c
  * @return {number[]}
  */
  var shortestToChar = function(s, c) {
  const res = []
  const indexList = []
  for(let i = 0; i < s.length; i++) {
      if(s[i] === c) {
          indexList.push(i)
      }
  }
  const getDistance = (list, index) => {
      let min = Number.MAX_VALUE;
      for(let i = 0; i < list.length; i++) {
          min = Math.min(Math.abs(list[i] - index), min)
      }
      return min
  }
  for(let i = 0; i < s.length; i++) {
      res.push(getDistance(indexList, i))
  }
  return res
  };

[wangqianqian202301]

思路

使用两个变量存储要查找的字符的位置，取距离两个字符的最小者

代码

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        length = len(s)
        lIndex = -length
        rIndex = s.index(c)
        rtnArr = [0 for i in range(length)]
        for i in range(len(s)):
            if s[i] == c:
                lIndex, rIndex = rIndex, i
                for j in range(lIndex + 1, rIndex):
                    rtnArr[j] = min(abs(j - lIndex), abs(j - rIndex))

            else:
                rtnArr[i] = min(abs(i - lIndex), abs(i - rIndex))
        return rtnArr

复杂度

O(mn)

[Meisgithub]

思路：遍历一次得到左边和右边最接近字符c的下标，最后计算最近距离 class Solution { public: vector shortestToChar(string s, char c) { int n = s.size(); vector left(n); vector right(n); left[0] = s[0] == c ? 0 : -10000; right[n - 1] = s[n - 1] == c ? n - 1 : 20000; for (int i = 1; i < n; ++i) { if (s[i] == c) { left[i] = i; } else { left[i] = left[i - 1]; } // cout << n - i - 1 << endl; if (s[n - i - 1] == c) { right[n - i - 1] = n - i - 1; } else { right[n - i - 1] = right[n - i]; } } vector ans(n); for (int i = 0; i < n; ++i) { ans[i] = min(abs(i - left[i]), abs(right[i] - i)); } return ans; } }; 时间复杂度：O(n) 空间复杂度：O(n)

[Abby-xu]

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

[FlipN9]

/**
    思路:     对每一个 i 从中心扩散找最近的 C     O(n^2)
        ==>  空间换时间, 存储所有 c 的位置       O(nk), 出现 k 次
        ==>  Greedy, 只关心最近的 C ==> 正向遍历+反向遍历
    ------------------------------------------------------------------
    实现:
        两个数组 left 和 right 分别记录每个字符左/右侧出现的最后一个 C 字符的下标
        同时比遍历这两个数组, 计算距离最小值

    优化:    
        1. 只需要最近的 C, 所以看情况可以覆盖掉第一个数组的值
            case 1. 字符的左侧没有出现过 C 字符
            case 2. i - left > right - i
        2. 直接记录 C 与当前字符的距离, 而不是 C 的下标, 还可以省去最后遍历计算距离的过程

    TC: O(N), SC: O(1)      1ms
*/
class Solution {
    public int[] shortestToChar(String s, char c) {
        int N = s.length();
        int[] dist = new int[N];
        dist[0] = s.charAt(0) == c ? 0 : N;
        for (int i = 1; i < N; i++) {
            dist[i] = s.charAt(i) == c ? 0 : dist[i - 1] + 1;
        }
        for (int i = N - 2; i >= 0; i--) {
            dist[i] = Math.min(dist[i], dist[i + 1] + 1);  // 左侧距离 > 右侧距离, 未遇到 C 默认距离为 N
        }
        return dist;
    }
}

/**
    sliding window: 把 c 看成 s 的分割线
    XXXX | XXXX | XXXXXX

    TC: O(N), SC: O(1)
*/
class Solution1 {
    public int[] shortestToChar(String s, char c) {
        int N = s.length();
        int[] dist = new int[N];

        int l = s.charAt(0) == c ? 0 : N;
        int r = s.indexOf(c);
        for (int i = 0; i < N; i++) {
            dist[i] = Math.min(Math.abs(i - l), Math.abs(r - i));
            if (i == r) {
                l = r;
                r = s.indexOf(c, l + 1);
            }
        }
        return dist;
    }
}

[chanceyliu]

思路

两次遍历，从前往后，在从后往前取最小距离

代码

function shortestToChar(s: string, c: string): number[] {
  const n = s.length;
  const res = new Array(n).fill(0);

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

  for (let i = n - 1, idx = 2 * n; i >= 0; i--) {
    if (s[i] === c) {
      idx = i;
    }
    res[i] = Math.min(res[i], idx - i);
  }

  return res;
}

复杂度分析

• 时间复杂度：O(N) 其中 N 为数组长度
• 空间复杂度：O(1)

[Fuku-L]

思路

数组的正序遍历和倒序遍历。需要遍历两次，使用 indexof(ch, index)需要注意字符串不存在的情况，即返回-1。

代码

public class Q0821ShortestDistanceToACharacter {

    public static void main(String[] args) {
        Solution solution = new Q0821ShortestDistanceToACharacter().new Solution();
        int[] test1= solution.shortestToChar("loveleetcode", 'e');
        System.out.println(Arrays.toString(test1));;
    }

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

            for (int i = 0; i < s.length(); i++) {
                int a = s.indexOf(ch, i);
                int b = s.lastIndexOf(ch, i);
                if (a == i) {
                    res[i] = 0;
                } else {
                    res[i] = a>0&&b>0?Math.min(Math.abs(a - i), Math.abs(b-i)):a<0? Math.abs(b-i): Math.abs(a-i);
                    //if(a<0){
                    //    res[i] = Math.abs(b-i);
                    //} else if(b<0){
                    //    res[i] = Math.abs(a-i);
                    //} else {
                    //    res[i] = Math.min(Math.abs(a - i), Math.abs(b-i));
                    //}
                }
            }
            return res;
        }
    }
}

复杂度分析

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

[AstrKing]

思路

1.无脑两次遍历，正着一次，反着一次，然后再比较两次遍历后相同下标处的最小值即可
2.遍历的时候只考虑当前顺序，考虑不到的情况由下次反序遍历时来弥补

代码

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

    for (int i = 0, idx = -n; i < n; ++i) {
        if (s.charAt(i) == c) {
            idx = i;
        }
        ans[i] = i - idx;
    }

    for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
        if (s.charAt(i) == c) {
            idx = i;
        }
        ans[i] = Math.min(ans[i], idx - i);
    }
    return ans;
}

复杂度分析

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

[xb798298436]

getDistance(s, c) { let n = s.length; let res = []; let pos = -n; for (let i = 0; i < n; i++) { if (s[i] === c) { pos = i; } res[i] = i - pos; }

for (let i = n - 1; i >= 0; i--) {
  if (s[i] === c) {
    pos = i;
  }
  res[i] = Math.min(res[i], pos - i);
}

return res;

}

[jmaStella]

思路 从左到右loop一遍，记录左边离他最近的character。再从右到左loop一遍记录右边离他最近的character，两者取min。

代码

public int[] shortestToChar(String s, char c) {
        int[] answer = new int[s.length()];
        int index = -1;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == c){
                index = i;
            }
            if(index == -1){
                answer[i] = s.length();
            }else{
                answer[i] = i - index;
            }
            //System.out.println(s.charAt(i) + " " + answer[i]);
        }
        //System.out.println("==================");
        for(int i=s.length()-1; i>=0; i--){
            if(s.charAt(i) == c){
                index = i;
            }
            if(index >= i){
                answer[i] = Math.min(answer[i], index - i);
            }
            //System.out.println(s.charAt(i) + " " + answer[i]);
        }
        return answer;
}

复杂度 时间：O(N) N=s.length() 空间：O(1)

[Zoeyzyzyzy]

Thought

• thinking of how to get distance between c and s.charAt(i);
• go through the string twice 1 order and 1 reverse order;
• in order is to traverse c in left situation, for first part(left has no c): make idx to -n;
• reverse order is to traverse c in right situation, for last part(right has no c): make idx to 2*n;

• find minium.

  Code

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

  Complexity

  Time complexity : O(n), traverse twice

Space complexity : O(n) array with size n

[harperz24]

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

        # Find all index of c
        c_index = []
        for i, ch in enumerate(s):
            if ch == c:
                c_index.append(i)

        # Initialize the res arr and a pointer     
        res = [0] * len(s)
        p = 0

        # Deal with three situations:
        # when i < the first c's index
        for i in range(0, c_index[0]):
            res[i] = c_index[0] - i

        # when i >= the last c's index
        for i in range(c_index[-1], len(s)):
            res[i] = i - c_index[-1]

        # when first <= i < last
        for i in range(c_index[0], c_index[-1]):
            if i >= c_index[p + 1]:
                p += 1
            res[i] = min(i - c_index[p], c_index[p + 1] - i)

        return res

        # time: O(len(s)), traverse twice
        # space: len(c_index), max = len(s)

[airwalkers]

// 思路，从左向右扫描记录左侧最近下标入left数组，
// 从右向左扫描右侧最近下标入right数组
// 根据left，right数组以及i计算最近结果

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

        for (int i = 0, pre = -1; i < chars.length; i++) {
            if (chars[i] == c) {
                pre = i;
            }
            left[i] = pre;
        }

        for (int i = chars.length - 1, pre = -1; i >= 0; i--) {
            if (chars[i] == c) {
                pre = i;
            }
            right[i] = pre;
        }

        int[] res = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            if (left[i] == -1) {
                res[i] = right[i] - i;
            } else if (right[i] == -1) {
                res[i] = i - left[i];
            } else {
                res[i] = Math.min(i - left[i], right[i] - i);
            }
        }
        return res;
    }
}

[Horace7]

var shortestToChar = function(s, c) {
    let res = Array(s.length).fill(0);

    for (let i = 0; i < s.length; i++) {
        if (s[i] !== c) {
            res[i] = res[i - 1] === void 0 ? Infinity : res[i - 1] + 1;
        }
    }

    for (let i = s.length - 1; i >= 0; i--) {
         if (res[i] === Infinity || res[i + 1] + 1 < res[i]) {
             res[i] = res[i + 1] + 1;
         }
    }

    return res
};

[JasonQiu]

• Set last (last position of the character) to a large negative number
• Scan from the beginning. Distances to the nearest c in the left direction are calculated in this process. last will be updated at the position where c is found
• Set last to a large positive number
• Scan from the end of s. When distance to the nearest c in the right direction is shorter, update the answer with that distance. Again, last will be updated at the position where c is found

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        answer = []
        last = -16383
        for i in range(len(s)):
            if s[i] == c:
                last = i
            answer.append(i - last)
        last = 16384
        for i in range(len(s) - 1, -1, -1):
            if s[i] == c:
                last = i
            answer[i] = min(last - i, answer[i])
        return answer

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

[joemonkeylee]

思路

• 先找char的位置
• 第二遍算较小长度

代码

    public int[] ShortestToChar(string s, char c)
    {
        //记录c的位置
        List<int> targetArray = new List<int>();

        var charArray = s.ToCharArray();
        for (int i = 0; i < charArray.Length; i++)
        {
            if (charArray[i].Equals(c))
            {
                targetArray.Add(i);
            }
        }

        var res = new int[charArray.Length];
        int targetArrayIndex = 0;
        for (int i = 0; i < charArray.Length; i++)
        {
            if (targetArrayIndex < targetArray.Count() && i.Equals(targetArray[targetArrayIndex]))
            {
                res[i] = 0;
                targetArrayIndex++;
            }
            else
            {
                if (i < targetArray[0])
                {
                    res[i] = Math.Abs(i - targetArray[targetArrayIndex]);
                }
                else if (i > targetArray[targetArray.Count() - 1])
                {
                    res[i] = Math.Abs(i - targetArray[targetArrayIndex - 1]);
                }
                else
                {
                    res[i] = Math.Min(Math.Abs(i - targetArray[targetArrayIndex]), Math.Abs(targetArray[targetArrayIndex - 1] - i));
                }
            }
        }
        return res;
    }

复杂度分析

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

[Quieter2018]

思路 从左往右遍历计算距离，从右往左遍历，取最小值。

代码

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> dis(s.size());
        int c_idx_1=0;
        int c_idx_2=1;

        for(int i = 0;i<s.size(); i++){
            if(s[i]==c){
                c_idx_2 = i;
                dis[i]=0;
                for(int j=c_idx_1; j<i;j++){
                    dis[j]=abs(c_idx_2-j);
                }
                c_idx_1 =c_idx_2+1;
            }else{
                dis[i]=abs(c_idx_2-i);
            }
        }

        c_idx_1= s.size()-1;
        c_idx_2= s.size()-1;
        vector<int> dis_back(s.size());

        for(int i = s.size()-1;i>=0; i--){
            if(s[i]==c){
                c_idx_2 = i;
                dis[i]=0;
                for(int j=c_idx_1; j>i;j--){

                    dis_back[j]=abs(c_idx_2-j);
                }
                c_idx_1 =c_idx_2-1;
            }else{
                dis_back[i]=abs(c_idx_2-i);
            }
        }

        for(int i = 0;i<s.size(); i++){
            dis[i]= min(dis_back[i],dis[i]);
        }

    return dis;    

    }
};

复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(n)

[snmyj]

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

        vector<int> res;
        for(int i=0;i<n;i++){

            if(s[i]==c) res.push_back(0);
            else{
                 for(int p=1;;p++){
                     if(i+p<n){
                     if((s[i+p]==c)&&(i+p)<n) {
                         res.push_back(p);
                         break;
                     }
                     }
                     if(i-p>=0){
                    if((s[i-p]==c)&&(i-p)>=0){
                        res.push_back(p);
                        break;
                    }
                     }
                 }

            }

        }
        return res;
    }
};

T:O(NlogN); S:O(N);

[import-ant]

思路

• 将数组s中字符c出现的索引放到一个临时数组中。
• 遍历数组s，对于s中的每个元素，遍历存放索引的临时数组，去找abs(temp(j)-i)最小的那个值。

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    const length = s.length;
    const answer = new Array(length).fill(0);
    const temp = [];
    for(let i = 0;i < length;i ++){
        if(s[i] == c){
            temp.push(i);
        }
    }
    for(let i = 0;i < length;i ++){
        let t = Infinity
        for(let j = 0;j < temp.length;j ++){
            t = Math.min(Math.abs(temp[j]-i),t);
        }
        answer[i] = t;
    }
    return answer;
};

复杂度分析

令 n 为数组长度。k为数组中字符c的数量

• 时间复杂度：$O(n*k)$
• 空间复杂度：$O(k)$ ，忽略结果数组

[kangliqi1]

    public static int[] shortestToChar(String s, char c) {
// 字符串长度
    int len = s.length();
    //创建一个和字符串长度一样长的数组存储结果值
    int[] r = new int[len];
//从左遍历
    int pos = -10000;
for (int i = 0; i < len; i++) {
        if (s.charAt(i) == c) {
            pos = i;
        }
        r[i] = i - pos;
    }
//从右遍历
    pos = 10000;
    for (int i = len - 1; i >= 0; i--) {
        if (s.charAt(i) == c) {
            pos = i;
        }
        r[i] = Math.min(r[i], pos - i);
    }
    return r;
}

时间复杂度O(n)

[import-ant]

思路

两次遍历 定义answer数组

• 寻找s[i]距离左边最近的字符c的距离；应该从左往右遍历；双指针
• 寻找s[i]距离右边最近的字符c的距离；应该从右往左遍历；

未想出的点

• 一直执着于双指针的运用；

• 初始想法：一次遍历，三个变量，使用两个变量left，right；

• left记录s[i]左边最近的字符c的索引

• right记录s[i]右边最近的字符c的索引

• Math.min(i - left,right-i);

• 没有想到两次循环。

  代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    //两次遍历 
    // 找s[i]距离左边最近的字符c的距离  从左往右遍历
    //找s[i]距离右边最近的字符c的距离  从右往左遍历
    let length = s.length;
    let answer = new Array(length).fill(length+1);
    for(let i = 0,j=-1;i < length;i ++){
        if(s[i] == c){
            j = i;
        }
        if(j != -1) answer[i] = Math.abs(i - j);
    }
    for(let i = length - 1,j=-1;i >= 0;i--){
        if(s[i] == c){
            j = i;
        }
        if(j!=-1) answer[i] = Math.min(answer[i],Math.abs(j-i));
    }
    return answer;
};

复杂度分析

令 n 为数组长度。

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

[el1as7]

class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: l = r = 0 n = len(s) res = [n] * n flag = False
while r <= n - 1: if s[r] == c: res[r] = 0 while l <= r: res[l] = min(res[l], r - l) l += 1 r += 1 flag = True else: if flag: res[r] = res[r-1] + 1 r += 1 return res

[hshen202108]

 public int[] shortestToChar(String s, char c) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (chars[i] == c) {
                list.add(i);
            }

        }
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int k = n;
            for (int j = 0; j < list.size(); j++) {
                int b = Math.abs(i - list.get(j));
                k = k - b <= 0 ? k: b;
            }
            result[i] = k;
        }

        return result;

    }

复杂度

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

[chocolate-emperor]

class Solution {
public:
//每个字符的结果来自离它右侧和左侧最近的字符c中的较小值
//扫描两遍，第一遍更新所有c字符右侧字符的距离，第二遍更新所有c字符的左侧字符距离
    vector<int> shortestToChar(string s, char c) {
        int l = s.length();
        int dis = 0, i=0, j=l-1;
        vector<int>res(l,l);
        while(s[i]!=c && i<l)  i+=1;
        while(i <= l-1){
            if(s[i]==c) dis=i;
            res[i] = min(res[i],i-dis);

            i+=1;
        }

        while(s[j]!=c && j>=0)   j-=1;
        while(j>=0){
            if(s[j]==c) dis=j;
            res[j] = min(res[j],dis - j);

            j-=1;
        }   

        return res;  

    }
};

[franciszq]

思路

求最短距离，一维数据的话，需要从前往后，从后往前各自遍历一遍，然后每个位置，取较小的一个。

代码

class Solution
{
public:
    vector<int> shortestToChar(string s, char c)
    {
        vector<int> from_begin_length, from_end_length, res;
        int length_tmp = 999999;
        for (int i = 0; i < s.size(); ++i) {    // 从头遍历
            if (s[i] == c) {
                length_tmp = 0;
            } else {
                length_tmp++;
            }
            from_begin_length.emplace_back(length_tmp);
        }
        length_tmp = 9999999;
        for (int i = s.size() - 1; i >= 0; --i) {     // 从尾遍历
            if (s[i] == c) {
                length_tmp = 0;
            } else {
                length_tmp++;
            }
            from_end_length.emplace_back(length_tmp);
        }
        for (int i = 0; i < s.size(); ++i) {
            if (from_begin_length[i] < from_end_length[s.size() - i - 1]) {
                res.emplace_back(from_begin_length[i]);
            } else {
                res.emplace_back(from_end_length[s.size() - i - 1]);
            }
        }
        return res;
    }
};

复杂度

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

[texamc2]

func shortestToChar(s string, c byte) []int {
    res := make([]int, len(s))
    for i := 0; i < len(s); i++ {
    l, r := i, i
    for ; l >= 0 && s[i] != c; l = l - 1;{
    }
    for ; r < len(s) && s[i] != c; r = r+1; {
    }
    if l < 0 {
        res[i] = r - i;
     } else if r > len(s) {
        res[i] = i - l;
     } else {
         res[i] = min(i-l, r-i)
     }
     }
     return res
  }
  func min(a, b int) int {
      if a > b {
          return b
         }
       return a
   }

[WL678]

思路：

​ 既然需要查找距离当前位置最近的目标字符，一共有两种可能，左边最近或者右边最近，那么直观的想法是，每当遍历到一个字符，分别从左到字符串开头和从右到字符串末尾进行查找，最后将两边得到的最近的目标字符的距离进行比较，取最小值即可。当然会出现一些特殊情况，左边或者右边没有字符没有，或者目标字符只出现了一次，并且当前刚好遍历到该字符，此时两边都查找不到。

代码：C++

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

        int len = s.size();
        vector<int> dis(len);
        for(int i = 0; i < len;i++) {
            int left = 0;
            int right = 0;
            if(s[i] != c){
                //查找左边
                for(int j = i; j >= 0; j--){
                    if(s[j] == c){
                        left = i - j;
                        break;
                    }
                }
                if(!left){
                    left = -1;
                }
                //查找右边
                for(int j = i; j < len; j++){
                    if(s[j] == c){
                        right = j - i;
                        break;
                    }
                }
                 if(!right){
                    right = -1;
                }
                if(left == -1 || right == -1){
                   dis[i] = max(left,right);
                } else {
                    dis[i] = min(left,right);
                }
                cout <<"letf:"<< left << endl;
                cout <<"rigth:"<< right << endl;
            } else {
                dis[i] = 0;
            }

        }
        return dis;
    }
};

复杂度分析：

时间复杂度：for循环里面嵌套了两个循环，时间复杂度为O(n*(i)+n*(n-i))=O($n^2$)

空间复杂度：O(n)

[zhangyong-hub]

思路： 1、把c出现的位置记录； 2、s[i]循环求最小距离 时间复杂度（O(n*k)） 空间复杂度O(N)

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int>num_i;
        vector<int>res(s.length(),s.size());
        for(int i=0;i<s.length();i++)
        {
            if(s[i]==c)
                num_i.push_back(i);
            else
                continue;
        }

        for(int i=0;i<s.length();i++)
        {
            int dist=s.length();
            if(s[i]==c)
            {
                res[i]=0;
                continue;
            } 
            else
            {
                for(int j=0;j<num_i.size();j++)
                {
                    dist = abs(i-num_i[j]);
                    if(dist<res[i])
                        res[i]=dist;
                }
            }
        }
        return res;
    }
};

[FireHaoSky]

思路：

''' 遍历数组，从左起以数组最大长度计算，逐个递减，当遇到c的时候更新被减数 从右再遍历一遍，同之前的结果对比取最小值。 '''

解题 python

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

    idx = -n
    for i in range(0,n):
        if s[i] == c:
            idx = i

        ans[i] = i - idx

    idx = 2*n
    for i in range(n-1, -1, -1):
        if s[i] == c:
            idx = i

        ans[i] = min(ans[i], idx-i)

    return ans

复杂度分析：

''' 时间复杂度：for循环O（n） 空间复杂度：O（1） '''

[yuzmt]

思路

拿到每一个字符到目标字符的距离，然后再取出最短距离

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    var len = s.length;
    var res = [];
    for (var i = 0; i < len; i++) {
        var distance = [];
        for (var n = 0; n < len; n++) {
            if (s[n] === c) {
                distance.push(Math.abs(i - n));
            }
        }
        res.push(Math.min(...distance))
    }
    return res;
};

复杂度

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