821. 字符的最短距离
题目描述
1
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
2
3
示例 1:
4
5
输入: S = "loveleetcode", C = 'e'
6
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
7
说明:
8
9
- 字符串 S 的长度范围为 [1, 10000]。
10
- C 是一个单字符，且保证是字符串 S 里的字符。
11
- S 和 C 中的所有字母均为小写字母。
Copied!
前置知识
- 数组的遍历(正向遍历和反向遍历)
思路
这道题就是让我们求的是向左或者向右距离目标字符最近的距离。
我画了个图方便大家理解：
比如我们要找第一个字符 l 的最近的字符 e，直观的想法就是向左向右分别搜索，遇到字符 e 就停止，比较两侧的距离，并取较小的即可。如上图，l 就是 3，c 就是 2。
这种直观的思路用代码来表示的话是这样的：
Python Code:
1
class Solution:
2
def shortestToChar(self, S: str, C: str) -> List[int]:
3
ans = []
4
5
for i in range(len(S)):
6
# 从 i 向左向右扩展
7
l = r = i
8
# 向左找到第一个 C
9
while l > -1:
10
if S[l] == C: break
11
l -= 1
12
# 向左找到第一个 C
13
while r < len(S):
14
if S[r] == C: break
15
r += 1
16
# 如果至死没有找到，则赋值一个无限大的数字，由于题目的数据范围是 [1, 10000]，因此 -10000 或者 10000就够了。
17
if l == -1: l = -10000
18
if r == len(S): r = 10000
19
# 选较近的即可
20
ans.append(min(r - i, i - l))
21
return ans
Copied!
复杂度分析
- 时间复杂度：$O(N^2)$
- 空间复杂度：$O(1)$
由于题目的数据范围是 $10^4$，因此通过所有的测试用例是没有问题的。
但是实际上，我们可以在线性的时间内解决。这里的关键点和上面的解法类似，也是两端遍历。不过不再是盲目的查找，因为这样做会有很多没有必要的计算。
我们可以使用空间换时间的方式来解，这里我使用类似单调栈的解法来解，大家也可以使用其他手段。关于单调栈的技巧，不在这里展开，感兴趣的可以期待我后面的专题。
1
class Solution:
2
def shortestToChar(self, S: str, C: str) -> List[int]:
3
ans = [10000] * len(S)
4
stack = []
5
for i in range(len(S)):
6
while stack and S[i] == C:
7
ans[stack.pop()] = i - stack[-1]
8
if S[i] != C:stack.append(i)
9
else: ans[i] = 0
10
for i in range(len(S) - 1, -1, -1):
11
while stack and S[i] == C:
12
ans[stack.pop()] = min(ans[stack[-1]], stack[-1] - i)
13
if S[i] != C:stack.append(i)
14
else: ans[i] = 0
15
16
return ans
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
实际上，我们根本不需要栈来存储。原因很简单，那就是每次我们碰到目标字符 C 的时候， 我们就把栈全部清空了，因此我们用一个变量标识即可，具体参考后面的代码区。
如果碰到目标字符 C 的时候，不把栈清空，那么这个栈的空间多半是不能省的，反之可以省。
代码
代码支持：Python3，Java, CPP, Go, PHP
Python3 Code：
1
class Solution:
2
def shortestToChar(self, S: str, C: str) -> List[int]:
3
pre = -10000
4
ans = []
5
6
for i in range(len(S)):
7
if S[i] == C: pre = i
8
ans.append(i - pre)
9
pre = 20000
10
for i in range(len(S) - 1, -1, -1):
11
if S[i] == C: pre = i
12
ans[i] = min(ans[i], pre - i)
13
return ans
Copied!
Java Code：
1
class Solution {
2
public int[] shortestToChar(String S, char C) {
3
int N = S.length();
4
int[] ans = new int[N];
5
int prev = -10000;
6
7
for (int i = 0; i < N; ++i) {
8
if (S.charAt(i) == C) prev = i;
9
ans[i] = i - prev;
10
}
11
12
prev = 20000;
13
for (int i = N-1; i >= 0; --i) {
14
if (S.charAt(i) == C) prev = i;
15
ans[i] = Math.min(ans[i], prev - i);
16
}
17
18
return ans;
19
}
20
}
Copied!
CPP Code:
1
class Solution {
2
public:
3
vector<int> shortestToChar(string S, char C) {
4
vector<int> ans(S.size(), 0);
5
int prev = -10000;
6
for(int i = 0; i < S.size(); i ++){
7
if(S[i] == C) prev = i;
8
ans[i] = i - prev;
9
}
10
prev = 20000;
11
for(int i = S.size() - 1; i >= 0; i --){
12
if(S[i] == C) prev = i;
13
ans[i] = min(ans[i], prev - i);
14
}
15
return ans;
16
}
17
};
Copied!
Go Code:
1
func shortestToChar(S string, C byte) []int {
2
N := len(S)
3
ans := make([]int, N)
4
5
pre := -N // 最大距离
6
for i := 0; i < N; i++ {
7
if S[i] == C {
8
pre = i
9
}
10
ans[i] = i - pre
11
}
12
13
pre = N*2 // 最大距离
14
for i := N - 1; i >= 0; i-- {
15
if S[i] == C {
16
pre = i
17
}
18
ans[i] = min(ans[i], pre-i)
19
}
20
return ans
21
}
22
23
func min(a, b int) int {
24
if a < b {
25
return a
26
}
27
return b
28
}
Copied!
PHP Code:
1
class Solution
2
{
3
4
/**
5
* @param String $S
6
* @param String $C
7
* @return Integer[]
8
*/
9
function shortestToChar($S, $C)
10
{
11
$N = strlen($S);
12
$ans = [];
13
14
$pre = -$N;
15
for ($i = 0; $i < $N; $i++) {
16
if ($S[$i] == $C) {
17
$pre = $i;
18
}
19
$ans[$i] = $i - $pre;
20
}
21
22
$pre = $N * 2;
23
for ($i = $N - 1; $i >= 0; $i--) {
24
if ($S[$i] == $C) {
25
$pre = $i;
26
}
27
$ans[$i] = min($ans[$i], $pre - $i);
28
}
29
return $ans;
30
}
31
}
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 1yr ago