ShortestDistanceToACharacter [source code]

public class ShortestDistanceToACharacter {
static
/******************************************************************************/
class Solution {
    public int[] shortestToChar(String S, char C) {
        int N = S.length ();
        int[] left_next = new int[N], right_next = new int[N];
        // clever initial values: N is not big enough
        for (int i = 0; i < N; i++) {
            left_next[i] = S.charAt (i) == C ? i : (i - 1 >= 0 ? left_next[i - 1] : -2 * N);
        }
        for (int i = N - 1; i >= 0; i--) {
            right_next[i] = S.charAt (i) == C ? i : (i + 1 < N ? right_next[i + 1] : 2 * N);
        }
        // System.out.println (Printer.array (left_next));///
        // System.out.println (Printer.array (right_next));///
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = Math.min (i - left_next[i], right_next[i] - i);
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ShortestDistanceToACharacter.Solution tester = new ShortestDistanceToACharacter.Solution();
        String[] inputs = {
            "loveleetcode", "e",
            "abaa", "b",
        };
        int[][] answers = {
            {3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0},
            {1,0,1,2},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            String S = inputs[2 * i];
            // convert string to char!
            char C = inputs[2 * i + 1].charAt (0);
            int[] ans = answers[i], output = tester.shortestToChar (S, C);
            String output_str = Printer.array (output), ans_str = Printer.array (ans);
            System.out.printf (
                "%s and %c\n%s, expected: %s\n", 
                S, C, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

每一个位置建立一个左右lookup的array就行了, 然后用最小值合并起来;

UNFINISHED

uwi:

    class Solution {  
    public int[] shortestToChar(String S, char C) {  
        int n = S.length();  
        int[] a = new int[n];  
        Arrays.fill(a, 9999999);  
        for(int i = 0;i < n;i++){  
            if(S.charAt(i) == C){  
                a[i] = 0;  
            }  
        }  
        for(int i = 1;i < n;i++){  
            a[i] = Math.min(a[i], a[i-1] + 1);  
        }  
        for(int i = n-2;i >= 0;i--){  
            a[i] = Math.min(a[i], a[i+1] + 1);  
        }  
        return a;  
    }  
}

整体的思路跟我的差不多, 但是他的计算方法更加的inline; 而且他这个算法只用了3分钟就写出来了; 只能说人跟人的差距;

Problem Description

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.

Difficulty:Easy
Total Accepted:1.6K
Total Submissions:2.5K
Contributor:milu