题目描述
Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the shortest distance from s[i] to the character c in s.
代码
双向搜索(遍历)
c++版:
vector<int> shortestToChar(string s, char c) {
int n = s.size(), position = -n;
vector<int> res(n, n);
for (int i = 0; i < n; i++){
if (s[i] == c) position = i;
res[i] = i - position;
}
for (int i = position - 1; i >= 0; i--){
if (s[i] == c) position = i;
res[i] = min(res[i], position - i);
}
return res;
}
Python版:
def shortestToChar(self, s: str, c: str) -> List[int]:
n, position = len(s), -float('inf')
res = [n] * len(s)
# Py3里反着读的写法 ::-1
for i in list(range(n)) + list(range(n)[::-1]):
if (s[i] == c): position = i
#res[i] = i - position
res[i] = min(res[i], abs(position - i))
return res
DP 原理差不多,这样写就有状态转移方程res[x]
左边就跟res[i - 1] + 1比,右边就是和res[i + 1] + 1比。
vector<int> shortestToChar2(string S, char C) {
int n = S.size();
vector<int> res(n);
for (int i = 0; i < n; ++i)
res[i] = S[i] == C ? 0 : n; //如果当前位置是c就设为0,否则设为n.
for (int i = 1; i < n; ++i)
res[i] = min(res[i], res[i - 1] + 1);
for (int i = n - 2; i >= 0; --i)
res[i] = min(res[i], res[i + 1] + 1);
return res;
}
同Py格式
def shortestToChar(self, S, C):
n = len(S)
res = [0 if c == C else n for c in S]
for i in range(1, n):
res[i] = min(res[i], res[i - 1] + 1)
for i in range(n - 2, -1, -1):
res[i] = min(res[i], res[i + 1] + 1)
return res