ShortestWordDistanceOPT [source code]

public class ShortestWordDistanceOPT {
    public int shortestDistance(String[] words, String word1, String word2) {
        if (words == null || words.length == 0) return 0;
        int index1 = -1;
        int index2 = -1;
        int min = words.length - 1;
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (word1.equals(word)) {
                index1 = i;
                if (index1 != -1 && index2 != -1) {
                    min = Math.min(min, Math.abs(index1 - index2));
                }
            } else if (word2.equals(word)) {
                index2 = i;
                if (index1 != -1 && index2 != -1) {
                    min = Math.min(min, Math.abs(index1 - index2));
                }
            }
        }
        return min;
    }

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

这个是 submission 最优解, 2ms.

首先注意看一下, 直到这里为止见过的几个最优解的高手, 都习惯于一上来就是illegitimate input check, 这里这个也是;

optimization running min

我自己的版本的设计的一个大问题是, 始终不愿意 maintain 一个running min; 写代码的时候有想过, 但是当时的想法就是, 想要写的聪明一些, 需要 maintain 的东西越少越好: premature optimization is the root of all evil ;

尤其是这一类问题, 是一个类似 optimization 的问题, 是一定要, 或者说几乎是一定要 maintain 一个running
opt的;

甚至严格来说, 他这里这个index1 and index2都不算是 maintain 的 opt, 而是两个普通的 pointer 而已;

仔细想想, 这个算法的核心好像是bottom-up DP; min 认为是the min distance just before the ith iteration; 然后整个算法就很好理解了;

我自己那个算法设计失败的原因, 好像是因为我对于 DP 的理解还不够深入. 我认为 DP 维护的是两个 index, 但是这个是不对的: 这个不满足DP property: 知道了 substring 的两个 index, 完全不代表你就知道了bigger string的optimal indices!
而且往往DP 维护的还是一个 value 的情况多一些(?这个好像有待考证);

这个也就是了为什么他这里每一个 iteration 第一步一上来就是udpate index 1 and index2. 其实就是强制进行DP decision而已;

冲这个问题就感觉 premium 买的值了, 非常加强对于 DP 的理解;

思考视觉模型

这个题目思考的时候, 脑子里的 visualizatoin 是:
a c b b a
\
\
\
a c b b a

这样一个 visualization 或许可以适用于大量类似的distance in place的题目;

题外话:
这个是 discussion 最优解:

public int shortestDistance(String[] words, String word1, String word2) {  
    int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;  

    for (int i = 0; i < words.length; i++) {  
        if (words[i].equals(word1))   
            p1 = i;  

        if (words[i].equals(word2))   
            p2 = i;  

        if (p1 != -1 && p2 != -1)  
            min = Math.min(min, Math.abs(p1 - p2));  
    }  

    return min;  
}

这个算法虽然看上去跟上面的算法差不多, 但是其实速度严重不如上面的算法, 自己想想为什么;

另外这里是另外一个优化:

public int shortestDistance(String[] words, String word1, String word2) {  
   int index = -1, minDistance = Integer.MAX_VALUE;  
   for (int i = 0; i < words.length; i++) {  
      if (words[i].equals(word1) || words[i].equals(word2)) {  
         if (index != -1 && !words[index].equals(words[i])) {  
            minDistance = Math.min(minDistance, i - index);  
          }  
          index = i;  
      }  
   }  
   return minDistance;  
}

这个优化完成的内容是只 maintain 一个 index. 其实差别不大, 因为我们本来要维护的是两个occurrence index, 所以把两个 index 合并之后, 只要增加一个equality check, 就可以区分是哪个的 occurence 了;

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