这是悦乐书的第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<n; i++) {
if (S.charAt(i) == C) {
continue;
}
// 向右寻找C
int right = i+1;
while (right < n && S.charAt(right) != C) {
right++;
}
// 如果当前字符一直向右寻找都找不到C，
// 就将其距离赋值为字符串的长度
if (right < n) {
result[i] = right-i;
} else {
result[i] = n;
}
// 向左寻找C
int left = i-1;
while (left >= 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<n; i++) {
// 遇到C，更新prev、next两个变量的值
if (i == next) {
prev = next;
next = S.indexOf(C, prev+1);
}
result[i] = Math.min(i-prev, Math.abs(i-next));
}
return result;
}
04 小结
算法专题目前已日更超过五个月，算法题文章191+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！