这是悦乐书的第321次更新，第343篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第191题（顺位题号是821）。给定字符串S和字符C，返回一个整数数组，表示字符串中所有字符到字符C的最短距离。例如：

输入：S =“loveleetcode”，C ='e'

输出：[3,2,1,0,1,0,0,1,2,2,1,0]

注意：

• S字符串长度为[1,10000]。

• C是单个字符，存在于字符串S中。

• S和C中的所有字母都是小写的。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

根据题目给的示例，当字符串中的字符和给定的字符相等时，距离为0，不相等时，距离会取该字符到左右相近的给定字符的距离中的最小值。

因此，我们可以直接遍历字符串中的字符，如果为给定字符就跳过，不为给定字符，就从当前字符所在的位置开始，分别向左和向右寻找给定字符，然后计算两边的距离，取两者之间的最小值即可。在向两边查找C时，需要注意字符串中字符下标边界不能越界的情况。

public int[] shortestToChar(String S, char C) {    int n = S.length();    int[] result = new int[n];    for (int i=0; i
    
     = 0 && S.charAt(left) != C) {            left--;        }        // 计算距离，前提是left要大于等于0        if (left >= 0) {            result[i] = Math.min(i-left, result[i]);        }    }    return result;}
    

03 第二种解法

依旧是利用向左向右计算距离的思路，但是此解法更加简洁。第一种解法中，每次都需要取向左向右查找C的位置，但是C所在的位置是固定的，只有当遇上C的时候，才会跳到下一个C那里，所以我们可以使用两个临时变量，将前一次C的位置和下一次C的位置存起来，遇到C就更新两个变量的值，另外不管遇不遇上C，都要计算当前字符与C的最近距离。

public int[] shortestToChar2(String S, char C) {    int prev = -10001, next = S.indexOf(C), n = S.length();    int[] result = new int[n];    for (int i=0; i

04 小结

算法专题目前已日更超过五个月，算法题文章191+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！