题目地址
难度：⭐
题目描述：
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
示例1：
1
2
| 输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
|
说明:
- 字符串
S 的长度范围为 [1, 10000]。
C 是一个单字符，且保证是字符串 S 里的字符。S 和 C 中的所有字母均为小写字母。
🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️解题过程🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️
解题过程：
思路：
定义结果数组result初始化为0（默认最短距离为0），遍历字符串S，对每一个字符先判断是否是指定字符C，若是则继续遍历下个字符，从0开始判断与当前字符左右距离为dis的字符是否是C，若是则把距离存到result数组中，然后继续遍历下个字符。
c++代码：(执行用时0ms，击败100.00%，内存消耗6.9M，击败39.62%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<int> shortestToChar(string S, char C) {
int n=S.length();
vector<int> result(n,0);
for(int i=0;i<n;++i){
if(S[i]==C){
continue;
}
int dis=0;
while(1){
++dis;
if(i-dis>=0&&S[i-dis]==C || i+dis<n&&S[i+dis]==C){
break;
}
}
result[i]=dis;
}
return result;
}
};
|
方法 1：最小数组
想法
对于每个字符 S[i]，试图找出距离向左或者向右下一个字符 C 的距离。答案就是这两个值的较小值。
算法
从左向右遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 i - prev。
从右向左遍历，记录上一个字符 C 出现的位置 prev，那么答案就是 prev - i。
这两个值取最小就是答案
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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)$，其中 $N$ 是
S 的长度，我们需要遍历字符串两次。
- 空间复杂度：$O(N)$，
ans 数组的大小
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：
官方题解比较巧妙，线性时间复杂度，效率比较高。虽然我也想到计算左右两边距离取最小，但是我想到的还是要遍历对每个字符遍历左右两边所有字符直到找到指定字符C，官方题解就巧妙的利用一次遍历线性复杂度就解决了，牛逼🐂
