ShortestWordDistance [source code]

public class ShortestWordDistance {
    public int shortestDistance(String[] words, String word1, String word2) {
        int dis1 = helper(words, word1, word2);
        for (int i = 0; i < words.length / 2; i++) words[i] = words[words.length - 1 - i];
        int dis2 = helper(words, word1, word2);
        return Math.min(dis1, dis2);
    }

    public int helper(String[] words, String word1, String word2) {
        int first = -100, second = -100;  //tricky initialization
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                if (second == -100 && i > first) {
                    first = i;
                    continue;
                }
                if (first > second) continue;
                if (Math.abs(i - second) < Math.abs(first - second)) first = i;
                continue;
            }
            if (words[i].equals(word2)) {
                if (first == -100 && i > second) {
                    second = i;
                    continue;
                }
                if (second > first) continue;
                if (Math.abs(i - first) < Math.abs(first - second)) second = i;
            }
        }
        return Math.abs(first - second);
    }

    public static void main(String[] args) {
        ShortestWordDistance tester = new ShortestWordDistance();
        String[] input1 = {"a", "b"};
        String[] input2 = {"a", "c", "b", "b", "a"};
        System.out.println(tester.shortestDistance(input2, "a", "b"));
    }
}

乍一看,这个题目的思路很简单, 但是这个题目其实难点要考虑 word1和 word2都出现多次的情况;

比较暴力的做法是把所有出现的 index 都记录下来, 然后数学处理就行了; 比如 word1出现在1,3, word2出现在2,6, 那么最小距离就是1;

这里我设计的这个算法虽然没有用数学处理的思路, 不过其实也是一个暴力解, 只不过看起来稍微有点复杂而已, 最后的速度很差, 600ms+, 惨不忍睹;//后来发现是 println 忘记删了. 删了之后是5ms, 其实不是不能接受;

设计这个算法当时的思路是假设在just before the ith iteration的瞬间, first 和 second 分别代表word1和 word2出现的位置so that distance is minimum; 然后对应的更新 first 和 second 就行了;
但是这个算法是有问题的, 这里的 input2就把这个算法给 break了;
最后的解决办法是words 倒过来再做一次.

这里一个小问题, 刚开始写的时候, equals又忘记用了, 直接用的==, 这个在自己本地跑是没问题的, 但是在 oj 上就死活过不了;

另外注意这里 println 的位置: 因为每一个iteration 的 exit 太多了, 所以按照传统的思路, 每一个 exit 配备一个 println, 就太麻烦了, 一个另外的方法就是干脆在每一个 iteratoin 最开头的地方 println, 其实是等效的(除了少数boundary case);

总体这个算法虽然对于锻炼思考有帮助, 不过速度还是太差了

Problem Description

Given a list of words and two words word1 and word2, return the shortest distance between these
two words in the list.

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

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

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Difficulty:Easy
Category:Algorithms
Acceptance:51.93%
Contributor: LeetCode
Topics:
Array
You might like:
(M) Shortest Word Distance II (M) Shortest Word Distance III
Company:
LinkedIn