This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #821 (Easy): Shortest Distance to a Character
Description:
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
.
Examples:
Example 1:  

Input:  s = "loveleetcode", c = "e" 
Output:  [3,2,1,0,1,0,0,1,2,2,1,0] 
Example 2:  

Input:  s = "aaab", c = "b" 
Output:  [3,2,1,0] 
Constraints:
1 <= s.length <= 10^4

s[i]
andc
are lowercase English letters. 
c
occurs at least once ins
.
Idea:
Since this problem is asking us to reference characters both ahead and behind the current charcter, this should bring to mind a twopass dynamic programming solution. We can iterate through the input string (S) once and fill our answer array (ans) with the distance from the preceeding occurrence of C.
Then we can iterate backwards through S again so that we can pick the best result between the value we obtained in the first pass with the distance from the preceeding C going the opposite direction.
Javascript Code:
The best result for the code below is 80ms / 39.0MB (beats 99% /100%).
var shortestToChar = function(S, C) {
let len = S.length, ans = new Uint16Array(len)
ans[0] = S.charAt(0) === C ? 0 : 10001
for (let i = 1; i < len; i++)
ans[i] = S.charAt(i) === C ? 0 : ans[i1] + 1
for (let i = len  2; ~i; i)
ans[i] = Math.min(ans[i], ans[i+1] + 1)
return ans
};
Python3 Code:
The best result for the code below is 28ms / 14.3MB (beats 99% / 86%).
class Solution:
def shortestToChar(self, S: str, C: str) > List[int]:
ans = []
ans.append(0 if S[0] == C else 10001)
for i in range(1,len(S)):
ans.append(0 if S[i] == C else ans[i1] + 1)
for i in range(len(S)2,1,1):
ans[i] = min(ans[i], ans[i+1] + 1)
return ans
Java Code:
The best result for the code below is 1ms / 38.8MB (beats 97% / 93%).
class Solution {
public int[] shortestToChar(String S, char C) {
int len = S.length();
int[] ans = new int[len];
ans[0] = S.charAt(0) == C ? 0 : 10001;
for (int i = 1; i < len; i++)
ans[i] = S.charAt(i) == C ? 0 : ans[i1] + 1;
for (int i = len  2; i >= 0; i)
ans[i] = Math.min(ans[i], ans[i+1] + 1);
return ans;
}
}
C++ Code:
The best result for the code below is 0ms /6.5MB (beats 100% / 97%).
class Solution {
public:
vector<int> shortestToChar(string S, char C) {
int len = S.length();
std::vector<int> ans;
ans.push_back(S[0] == C ? 0 : 10001);
for (int i = 1; i < len; i++)
ans.push_back(S[i] == C ? 0 : ans[i1] + 1);
for (int i = len  2; i >= 0; i)
ans[i] = min(ans[i], ans[i+1] + 1);
return ans;
}
};
Top comments (0)