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

[zhiyuanpeng]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        # compute the dis from its left 
        ans = []
        pre = float("-inf")
        for i in range(len(s)):
            if s[i] == c:
                pre = i
            ans.append(i-pre)
        pre = float("inf")
        for i in range(len(s)-1, -1, -1):
            if s[i] == c:
                pre = i
            ans[i] = min(ans[i], pre-i)
        return ans

two passes: 1. compute the dis from its left 2. compute the dis from its right, the val is min(ans[i], pre-i)

time: n, space 1

[coderXiaowq]

Java 时间复杂度O(n)

public int[] shortestToChar(String s, char c) {
        int[] rs = new int[s.length()];
        char[] a = s.toCharArray();
        //记录字符c出现在i"左边""的最近索引left<=i,第1次可能例外
        int left = s.indexOf(c+""); 
        for(int i = 0; i < a.length; i++){
            char ch = a[i];//记录当前索引i位置的字符
            if(ch == c){
                rs[i] = 0;
                left = i;
                continue;
            }else if(left > i){//left大于i,因为left是i"左边"的,所以不存在更近的右边索引了
                rs[i]= left-i;
                continue;
            }
            //运行到这里,说明left<i,需要查询i右边
            int right = i + 1;
            while(right < a.length && a[right] != c){
                right++;
            }
            //找到i右边的第一个目标right, a[right]==c
            if(right == a.length){//right越界
                rs[i] = i - left;
            }else{
                rs[i]= Math.min(i-left,right-i);
            }

        }
        return rs;
    }

[xil324]

from left to right: startIndex = 11 [l,o,v,e,l,e,e,t,c,o,d,e] [11,10,9,0,1,0,0,1,2,3,4,0]

from right to left: startIndex = 0 [3,2,1,0,1,0,0,4,3,2,1,0]

compare two arrays to get the min

var shortestToChar = function(s, c) {
    const res = []; 
    let index = s.length - 1; 
    for(let i = 0; i < s.length; i++) {
        if(s[i] === c) index = i;
        res[i] = Math.abs(index - i);  
    }

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

    return res; 

};

time complexity: O(n) space complexity: O(n)

[RocJeMaintiendrai]

思路

对数组进行两次遍历。 第一次从左向右使用一个指针来记录最靠近当前字母左边的c的位置，并记录下距离。 第二次从右向左同样使用指针来计算当前字母与最靠近的右边的c的距离并与第一次遍历的结果进行对比取最小值。

代码

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

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

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

        return res;
    }
}

复杂度分析

• 时间复杂度：O(2N)，两次遍历
• 空间复杂度：O(1)

[atom-set]

思路

• 基本思想：从题目里可以得知，会用到回溯思想：字符 C 出现不止一次，当第 N + 1 次 (N >=1) 出现时，需要进行判断第 N + 1 次出现的位置和 第 N 次出现的位置之间的元素距离进行比对，取最小的那个距离。
• 数据结构
  • 栈: 结果存到到堆栈里，因为回溯会用到数据结果栈
  • 队列: 从栈顶弹窗的元素，再次进栈需要用队列，先出栈的元素先进栈

代码

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function (s, c) {
  // 存放结果
  var res = [];
  var targetPos = -1;

  // step1: 先将 s 转换成数组
  var sArr = s.split("");

  // step2: 遍历 sArr
  for (var i = 0; i < sArr.length; i++) {
    if (sArr[i] !== c) {
      // 长度默认设置为 1
      res.push(
        targetPos === -1
          ? 10000
          : Math.abs(i - (targetPos === -1 ? 0 : targetPos))
      );
      continue;
    }
    console.log("step1: res:", res, targetPos, i);

    if (sArr[i] === c) {
      var tempArr = [];
      // 先出栈到距离为0的元素
      while (res.length > 0 && res[res.length - 1] !== 0) {
        tempArr.unshift(res.pop());
      }
      console.log("step2: tempArr:", tempArr);

      // 再次进栈校验距离
      while (tempArr.length > 0) {
        var len = tempArr.length;
        const head = tempArr.shift();
        console.log("head:", head);
        if (head > len) {
          res.push(len);
        } else {
          res.push(head);
        }
      }
      res.push(0);
      console.log("step3: res:", res, targetPos, i);
      targetPos = i;
      continue;
    }
  }

  return res;
};

复杂度分析

空间复杂度取决于临时队列的长度，即 O(N)

时间复杂度取决于回溯元素的长度，即 O(N)，遍历的时间复杂度也是 O(N)，这 2 个是叠加关系，及时间复杂度是 O(N)

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

[zin-next]

题解

function shortestToChar(s, c) {
  var arr = new Array(s.length);
  var left = -Infinity
  var right = s.indexOf(c)
  for (var i = 0; i < s.length; i++) {
    if(i === right){
      left = right
      right = s.indexOf(c, right+1)
    }
    arr[i] = Math.min(right < 0 ? Infinity : right - i, i - left)
  }
  console.log(arr)
  return arr
}

复杂度分析

双指针，只有一次循环，时间复杂度O(n) 空间复杂度取决去数据规模 O(n)

[wwz223]

思路

采用双指针的方式进行求解，分别从两个方向进行遍历，头部 -> 尾部，尾部 -> 头部，通过取最小值的方式将之前保存的距离进行覆盖

代码

  let i = 0;
  let k = s.length - 1;
  let iKey = -1;
  let kKey = -1;
  let arr = [];
  while (i < s.length) {
    if (s[i] !== c) {
      arr[i] = Math.min(iKey >= 0 ? i - iKey : 10000, arr[i] || 10000);
    } else {
      iKey = i;
      arr[i] = 0;
    }
    if (s[k] !== c) {
      arr[k] = Math.min(kKey >= 0 ? kKey - k : 10000, arr[k] || 10000);
    } else {
      kKey = k;
      arr[k] = 0;
    }
    i++;
    k--;
  }
  return arr;
};

复杂度分析

时间复杂度：使用了一层循环 O(N) 空间复杂度：创建了一个数组和多个变量，数组长度为s的长度 O(N)

[borderGong]

代码

var shortestToChar = function(s, c) {
    const flag = 100000;
    const n = s.length;
    const answer = new Array(n).fill(flag);

    let prev = -flag;
    for (let i = 0; i < n; i++) {
        if (s[i] === c) {
            prev = i;
        }
        answer[i] = Math.min(answer[i], Math.abs(i - prev));
    }

    prev = flag;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] === c) {
            prev = i;
        }
        answer[i] = Math.min(answer[i], Math.abs(i - prev));
    }

    return answer;
};

思路

通过两次遍历字符串 s，分别从左到右和从右到左，更新每个位置到字符 c 最近位置的距离，最终得到最短距离数组并返回。

[CathyShang]

思路： 两次遍历，a.一次求字符串元素s[i]到其右侧目标字符的距离最小值；b. 另一次求字符串元素s[i]到其左侧目标字符距离； 距离通过索引相减获得。 代码：

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int i=0;
        int b=0; // 上一个同字符索引
        int n = s.length();
        std::vector<int> temp(n);
        int cur;
        // 到右侧 同字符距离 n
        while( s[i]!='\0'){
            if(s[i]==c){
                temp[i]=0;
                for(int j = b; j<i; j++){
                    cur = i-j;
                    if(temp[j] > cur){temp[j] = cur;}          
                }
                b = i;}
            else{temp[i]=n;}
            i++;
        }
        // 到左侧 同字符距离
        for(int i = 0, b= -n; i<n; ++i){
            if(s[i]==c){
                b = i;
            }
            temp[i] = min(temp[i], i-b);
            // std::cout << temp[i]<<'\n';
        }
        return temp;
    }
};

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

[GReyQT]

题解思路： （1）获取字符串的下标存在在结果数组中，及字符C的下标存在在数组中 （2）使字符串的下标数组减去字符C的下标数组并取最小值 代码：

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> ac,res;
        int length = s.size();
        for(int i=0; i < length; ++i)//获取字符串的下标，及字符C的下标
        {
            res.push_back(i);
            if(c == s[i])
                ac.push_back(i);
        }
        for(auto it = res.begin(); it != res.end(); ++it)//使字符串的下标减去字符C的下标并取最小值
        {
            int min = length;
            for(auto at = ac.begin(); at != ac.end(); ++at)
            {
                int temp = abs((*it)-(*at));
                if(min >= temp)
                    min = temp;
            }
            *it = min;
        }
        return res;
    }
};

复杂度分析： 时间复杂度：取决于字符串的长度n和目标字符 c 的数量m，因此为O(n*m) 空间复杂度：取决于字符串的长度n对应的结果vector，因此为O(n)

[YANGLimbo]

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        // 只想出来两个循环嵌套的暴力
        int len = s.size();
        vector<int> ans(len, len-1);
        auto absDiff = [](int a, int b) -> int{
            if(a>b){
                return a-b;
            }
            return b-a;
        };
        for(int i = 0; i < len; i++){
            char elem = s[i];
            if(elem == c){
                ans[i] = 0;
            }else{
                for(int j = 0; j < len; j++){
                    char temp = s[j];
                    if(temp == c){
                        ans[i] = min(ans[i], absDiff(i,j));
                    }
                }    
            }
        }
        return ans;
    }
};

[Hawkins-hjq]

思路

暴力求解法：两次遍历，求最短距离；

代码

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

        for(int j =0;j<s.length();j++){
           int distance = 10000;
           for(int k =0;k<posList.size();k++){
                if(Math.abs(j-posList.get(k))<distance){
                    distance = Math.abs(j-posList.get(k));
                }
           }
           result[j] = distance;
        }

        return result;
    }
}

复杂度

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

[rao-qianlin]

• 思路：正向反向遍历两次，取距离的最小值

class Solution {
    public int[] shortestToChar(String s, char c) {
        char[] sc = s.toCharArray();
        int count = -1;
        int[] de = new int[sc.length];
        // 正向遍历计算一次值
        for(int i=0; i<sc.length; i++){
            if(sc[i] ==c){
                count = i;
            }
            if(count == -1){
                // 表示还没有遇到第一个c
                de[i] = sc.length;
            }
            else{
                de[i] = i-count;
            }
        }
        count = -1;
        // 反向遍历计算一次值
        for(int i=sc.length-1; i>=0; i--){
            if(sc[i] == c){
                count = i;
            }
            if(count != -1){
                de[i] = Math.min(count-i,de[i]);
            }
        }
        return de;
    }
}

[smallppgirl]

思路：遍历找到所有的c存入listc，然后遍历整个list依次计算所有绝对值差，找出最小的追加进入一个新的list

代码

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

时间复杂度： O(nm) #m 是c 的个数 空间： O(n)

[snmyj]

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

        index = -2*n; 
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                index = i;
            }
            ans[i] = i - index;
        }

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

[Alexzhang-Mini]

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        result = [0] * len(s)
        c_indices = [i for i in range(len(s)) if s[i] == c]
        for i in range(len(s)):
            min_distance = float('inf')
            for index in c_indices:
                distance = abs(index - i)
                min_distance = min(min_distance, distance)
            result[i] = min_distance
        return result

[hillsonziqiu]

思路

正反来回两次遍历，正向遍历是获取距离左侧c的距离，反向遍历是获取距离右侧c的距离。第二次遍历的时候对比正向过来的值获取最小值。

解法

var shortestToChar = function (s, c) {
  let res = [];
  const n = s.length;
  let mark = -n;
  for (let i = 0; i < n; i++) {
    if (s[i] === c) {
      mark = i;
    }
    res[i] = i - mark;
  }
  mark = 2 * n;
  for (let i = n - 1; i >= 0; --i) {
    if (s[i] === c) {
      mark = i;
    }
    res[i] = Math.min(res[i], mark - i);
  }

  return res;
};

复杂度分析

时间复杂度 O(n) 两次遍历 n+n 复杂度忽略常量 空间复杂度 O(1) 就用到一个常量

[Martina001]

两遍遍历可解，第一遍从左到右，第二遍从右到左，更新到e的较小值 根据题意 这道题很像是找e为终点的最短路径，直接套用BFS来求解

 private int[] bfs(String s,char c){
        int n = s.length();
        int res[] = new int[n];
        Arrays.fill(res,-1);
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0;i<n;i++){
            if(s.charAt(i) == c){
                queue.offer(i);
                res[i] =0;
            }
        }
        int []dir = new int[]{-1,1};
        while(!queue.isEmpty()){
            int index = queue.poll();
            for(int d:dir){
                int next = index+d;
                if(next >=0 && next<n && res[next] ==-1){
                    res[next] = res[index] +1;
                    queue.offer(next);
                }
            }
        }
        return res;
    }

每个数组只用入栈出栈一次，所以时间复杂度为On 用到了栈，所以空间复杂度为On

[pandapls]

var shortestToChar = function(s, c) { const result = []; let prev = -Infinity;

for(let i = 0; i < s.length; i++) {
    if (s[i] == c) {
        prev  = i
    }
    result[i] = i - prev
}

prev = Infinity;
for(let i = s.length - 1; i >= 0; i--) {
    if (s[i] == c) {
        prev = i
    }

    result[i] = Math.min(result[i], prev - i)
}

return result;

};

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