字符串数组中两个字符的最短距离

[leetcode] https://leetcode.com/problems/shortest-word-distance/ java

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].数组

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.spa

须要注意：code

1. 该数组中得字符串有可能出现屡次，好比例子中的makes;orm

这个问题比较简单，按照下面的步骤能够简单的作出来：leetcode

1. 记录给定两个字符串出现的位置，会获得两个数组；假设为a和b；字符串

2. 而后计算abs(a[i] - b[j])的最小值便可；get

第一步扫描一遍字符串数组便可；第二步，若是简单的用两层循环来作，由于a和b的长度都有多是n（好比各占一半），那么用O（n * n)的时间；it

事实上，有意思的地方就在于，第二步能够在线性时间内解出来；这里有一个隐藏的特性，扫描原数组的时候获得的两个字符的位置数组，是有序的；好比数组 [a, b, a, b, b, a], 那么a的位置数组为[0, 2, 5], b的为[1, 3, 4]; 假设咱们比较到了位置2和位置3，咱们是没有必要去比较位置2和4的；由于后者的距离确定大于前者；用下面的图可能更清楚；class

因此，能够获得这样的关系，当a < b的时候，增长a的坐标，当a > b的时候，增长b的坐标；这样就能够在o(n)的时间内完成；

public int shortestDistance(String[] words, String word1, String word2) {
    int[] indexes1 = new int[words.length];
    int[] indexes2 = new int[words.length];
    int m = 0, n = 0;
    for (int i = 0; i < words.length; i++) {
        String word = words[i];
        if (word.equals(word1)) {
            indexes1[m++] = i;
        } else if (word.equals(word2)) {
            indexes2[n++] = i;
        }
    }
    int dist = Integer.MAX_VALUE;

    for (int i = 0, j = 0; i < m && j < n; ) {
        int x = indexes1[i];
        int y = indexes2[j];
        dist = Math.min(dist, Math.abs(x - y));
        if (x < y) {
            i++;
        } else {
            j++;
        }
    }

    return dist;
}