[LeetCode] 821. Shortest Distance to a Character

轉自LeetCode

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:

1. S string length is in [1, 10000].
2. C is a single character, and guaranteed to be in string S.
3. All letters in S and C are lowercase.

<Solution>

想法如下

• 先從左到右掃一次，找出離在左邊的指定字元的最短距離

• 再從右到左掃一次，找出離在右邊的指定字元的最短距離，然後比較之前的距離找出答案

code 如下

Java(參考解法)

	class Solution {
	public int[] shortestToChar(String S, char C) {
	final int len = S.length();
	int[] ans = new int[len];
	//>> scan from left to right
	//>> find the shortest distance in the left
	int lastIdx = -len * 2;
	for(int i = 0; i < len; i++) {
	if(S.charAt(i) == C) {
	lastIdx = i;
	}
	else {
	ans[i] = i - lastIdx;
	}
	}
	//>> scan from right to left
	//>> find the shortest distance in the right ans compare with shortest distance in the left
	lastIdx = len * 2;
	for(int i = len - 1; i >= 0; i--) {
	if(S.charAt(i) == C) {
	lastIdx = i;
	}
	else {
	ans[i] = Math.min(ans[i], lastIdx - i);
	}
	}
	return ans;
	}
	}

view raw shortestToChar.java hosted with ❤ by GitHub