Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.
Example 1:
Input: S = "loveleetcode", C = 'e' Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
Note:
S string length is in [1, 10000]. C is a single character, and guaranteed to be in string S. All letters in S and C are lowercase.
public class Solution {
public int[] ShortestToChar(string S, char C) {
var left = new int[S.Length];
var right = new int[S.Length];
int j=int.MaxValue;
bool found = false;
for(int i=0;i<S.Length;i++){
if(S[i]==C){
j=0;
found=true;
}
else if(found){
j++;
}
left[i]=j;
}
j = int.MaxValue;
found = false;
for(int i=S.Length-1;i>=0;i--){
if(S[i]==C){
j=0;
found = true;
}
else if(found){
j++;
}
right[i]=Math.Min(left[i],j);
}
var res = new int[S.Length];
for(int i=0;i<S.Length;i++){
res[i]=Math.Min(left[i],right[i]);
}
return res;
}
}Time Complexity: O(n)
Space Complexity: O(n)
