https://leetcode.com/problems/shortest-distance-to-a-character/description/
https://leetcode.com/problems/shortest-distance-to-a-character/discuss/125788/C++JavaPython-Easy-and-Concise-with-Explanation
https://leetcode.com/problems/shortest-distance-to-a-character/discuss/126116/Concise-java-solution-with-detailed-explanation.-Easy-understand!!!
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;
}
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:
Sstring length is in[1, 10000].Cis a single character, and guaranteed to be in stringS.- All letters in
SandCare lowercase.
https://leetcode.com/problems/shortest-distance-to-a-character/discuss/125788/C++JavaPython-Easy-and-Concise-with-Explanation
public int[] shortestToChar(String S, char C) {
int n = S.length();
int[] res = new int[n];
int pos = -n;
for (int i = 0; i < n; ++i) {
if (S.charAt(i) == C) pos = i;
res[i] = i - pos;
}
for (int i = n - 1; i >= 0; --i) {
if (S.charAt(i) == C) pos = i;
res[i] = Math.min(res[i], Math.abs(i - pos));
}
return res;
}
We give it one more loop at first to find all character
C and initialize distance to 0. public int[] shortestToChar(String S, char C) {
int n = S.length();
int[] res = new int[n];
for (int i = 0; i < n; ++i) res[i] = S.charAt(i) == C ? 0 : n;
for (int i = 1; i < n; ++i) res[i] = Math.min(res[i], res[i - 1] + 1);
for (int i = n - 2; i >= 0; --i) res[i] = Math.min(res[i], res[i + 1] + 1);
return res;
}
/** "loveleetcode" "e"
* 1. put 0 at all position equals to e, and max at all other position
* we will get [max, max, max, 0, max, 0, 0, max, max, max, max, 0]
* 2. scan from left to right, if =max, skip, else dist[i+1] = Math.min(dp[i] + 1, dp[i+1]),
* we can get [max, max, max, 0, 1, 0, 0, 1, 2, 3, 4, 0]
* 3. scan from right to left, use dp[i-1] = Math.min(dp[i] + 1, dp[i-1])
* we will get[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
*/
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] dist = new int[n];
for (int i = 0; i < n; i++) {
if (s.charAt(i) == c) continue;
dist[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < n-1; i++) {
if (dist[i] == Integer.MAX_VALUE) continue;
else dist[i + 1] = Math.min(dist[i+1], dist[i] + 1);
}
for (int i = n-1; i > 0; i--) {
dist[i-1] = Math.min(dist[i-1], dist[i] + 1);
}
return dist;
}
Idea is exactly the same as other solutions using stack or two pointers. Keep track of the last seen target character C as well as a left pointer pointing to the last non C character.
If you hit a nonC character and have not seen any C yet, max out that value.
If you hit a nonC character and have seen a C, the current distance to C is the current position i minus the index of the last seen C.
If you hit a C, update all entries from the left pointer up until the current index with the correct value. This is the minimum between the distance to the current C and the previous distance to another C. Finally, update the last seen C index to the current index.
public int[] shortestToChar(String S, char C) {
int[] result = new int[S.length()];
int lastC = -1;
int lastNonC = 0;
for(int i = 0; i<S.length(); i++)
if(S.charAt(i) == C){
while(lastNonC<=i)
result[lastNonC] = Math.min(result[lastNonC], i-lastNonC++);
lastC = i;
}else
result[i] = lastC != -1 ? i-lastC : Integer.MAX_VALUE;
return result;
}
package com.lifelongprogrammer.interview;
class Solution {
public static void main(String[] args) {
}
public int[] shortestToChar(String str, char ch) {
int[] result = new int[str.length()];
int prevIdx = -1;
int curIdx = -1;
for (int i = 0; i < result.length; i++) {
if (str.charAt(i) == ch) {
curIdx = i;
result[i] = 0;
// handle prevIdx to currIdx
for (int j = Math.max(0, prevIdx); j < curIdx; j++) {
if (prevIdx == -1) {
result[j] = curIdx - j;
} else {
result[j] = Math.min(j - prevIdx, curIdx - j);
}
}
}
//
prevIdx = curIdx;
}
// case xx e (xxxx last part)
if (curIdx != str.length() - 1) {
for (int j = Math.max(0, prevIdx); j < str.length(); j++) {
result[j] = j - prevIdx;
}
}
return result;
}
For each index
S[i], let's try to find the distance to the next character C going left, and going right. The answer is the minimum of these two values.
Algorithm
When going left to right, we'll remember the index
prev of the last character C we've seen. Then the answer is i - prev.
When going right to left, we'll remember the index
prev of the last character C we've seen. Then the answer is prev - i.
We take the minimum of these two answers to create our final answer.
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;
}
