ShortestWordDistanceIII [source code]

public class ShortestWordDistanceIII {
static
/******************************************************************************/
public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int pt1 = 0, pt2 = 0;
        for (String word : words) {
            if (word.equals(word1))
                pt1++;
            if (word.equals(word2))
                pt2++;
        }
        int[] pos1 = new int[pt1], pos2 = new int[pt2];
        pt1 = 0;
        pt2 = 0;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1))
                pos1[pt1++] = i;
            if (words[i].equals(word2))
                pos2[pt2++] = i;
        }
        pt1 = 0;
        pt2 = 0;
        int minDist = words.length;
        while (pt1 < pos1.length && pt2 < pos2.length) {
            int dist = Math.abs(pos1[pt1] - pos2[pt2]);
            if (dist < minDist && dist != 0)
                minDist = dist;
            if (pt1 + 1 < pos1.length && pt2 + 1 < pos2.length) {
                if (Math.abs(pos1[pt1 + 1] - pos2[pt2]) < Math.abs(pos1[pt1] - pos2[pt2 + 1]))
                    pt1++;
                else
                    pt2++;
            } else if (pt1 + 1 < pos1.length) {
                pt1++;
            } else {
                pt2++;
            }
        }
        return minDist;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ShortestWordDistanceIII.Solution tester = new ShortestWordDistanceIII.Solution();
        String[][] inputs = {
            {"practice", "makes", "perfect", "coding", "makes"}, {"makes", "coding"}, {"1"},
            {"practice", "makes", "perfect", "coding", "makes"}, {"makes", "makes"}, {"3"},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String[] words = inputs[3 * i];
            String word1 = inputs[1 + 3 * i][0], word2 = inputs[1 + 3 * i][1];
            int ans = Integer.parseInt(inputs[2 + 3 * i][0]);
            System.out.println(Printer.seperator());
            int output = tester.shortestWordDistance(words, word1, word2);
            System.out.println(
                Printer.wrapColor(Printer.array(words) + " AND " + word1 + " + " + word2, "magenta") +
                " -> " + output +
                Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
                );
        }
    }
}

老规矩, 这个题目给了例子, 先直接脑子里仔细完整的跑一下例子, 体现一下人逻辑(不要因为你大概看看就能知道, 有些细节你大概看看是无法体会的; 尤其是大部分不是太简单的题目, 真正里面你逻辑设计的时候都是有坑的, 这个坑也是你重点需要照顾的东西, 很可能一个看起来甚至像Corner Case的小坑会让你的整个逻辑和代码都必须要变样);

想了一下, 这个问题其实等价于一个给你两个ascending数组, 然后找出两个数组当中距离最小的两个数, 每个数组出一个数. 这个题目做过吗? 好像很熟悉, 就算没做过好像也是一个经典问题;

这个问题就是这个题目看起来多了一个duplicate的条件的小变形, 但实际上整个问题的本质都变化了;

穷搜肯定不行的, N^2的复杂度;

原来真是一个经典问题: http://www.geeksforgeeks.org/given-two-sorted-arrays-number-x-find-pair-whose-sum-closest-x/ . G4G上面是有这个题目的;

不对好像不是一回事; //但是思路好像可以借用;

不对, 不够完整, 找到一个更加类似的: https://stackoverflow.com/questions/24989772/finding-closest-numbers-within-two-arrays

sort two lists  
let i = 0, j = 0, minval = abs(list1[0] - list2[0])  
as long as both lists have more items:  
  minval = min(minval, abs(list1[i] - list2[j])  
  if abs(list1[i + 1] - list2[j]) < abs(list1[i] - list2[j + 1])  
     increment i  
  else increment j

这个就很像话了;

最后在这个提示之下, 还是做出来了这个题目.

这个题目给我一个教训, 比如我当时看到这个find closest pair from two arrays的问题的时候, 我就已经有点想放弃了. 不过后来想了想还是先Google; 最后代码也写出来了, 我感觉这个也是挺好的, 是一个锻炼的机会, 是比你直接看代码要好的;

这个算法最后的速度是5(12), 不是很满意, 感觉这个其实已经很快了; 可能是题目比较老的原因?

这个算法做的时候, 首先我先不考虑两个要搜索的word相同的情况, 然后按照closest pair的算法写了一个算法, 然后回过头来再来解决两个word相等的情况(要熟悉这种设计算法的思路). 面临一个抉择, 如果我们单独给word相等的情况写一个单独的函数, 是很好写的; 但是有必要吗? 有没有可能直接在当前的代码里面整合进去? 稍微分析了一下第二个input之后, 发现是可以的, 改动是这样的:

头两个for循环, 也就是build pos1 pos2的两个循环, 里面的逻辑用两个if, 但是不要用else连接; 这样在word相等的情况下, 两个pos array都有正确的大小和内容;
最后一个while循环, 在判断dist是否足够触发更新的时候, 除了判断dist < minDist, 还要判断dist大于0; 这样相同index的情况就直接排除了;

另外两个小的需要注意的地方:

最开始build两个pos的过程是可以用Map来做的, 不过感觉用array直接做也不是很难就直接用array来做了, 虽然最后并没有获得很好的加速效果;
注意pt1和pt2两个指针更新部分的写法; 这个算是这个算法稍微难一点的部分了; 注意探路之前要先判断是否出界(用&& in header的技巧);

总体来说这个算法写法上的细节不难, 关键是要想到把这个问题拆分成你能够解决的基本问题, 然后套用已有结论. 这个套路其实还是比较符合middle问题的难度的;

不过感觉discussion应该有比我这个更好的解法;

这个题目我刚开始的想法肯定还是一个1pass的历史信息流就搞定, 但是因为两个key可能出现多次, 所以普通的只保存一个index的历史信息流做法就不太好做; 当时就放弃这个想法了, 感觉做不过来;

这个是Stefan po的一个解法:

i1 and i2 are the indexes where word1 and word2 were last seen. Except if they're the same word, then i1 is the previous index.

public int shortestWordDistance(String[] words, String word1, String word2) {  
    long dist = Integer.MAX_VALUE, i1 = dist, i2 = -dist;  
    for (int i=0; i<words.length; i++) {  
        if (words[i].equals(word1))  
            i1 = i;  
        if (words[i].equals(word2)) {  
            if (word1.equals(word2))  
                i1 = i2;  
            i2 = i;  
        }  
        dist = Math.min(dist, Math.abs(i1 - i2));  
    }  
    return (int) dist;  
}

这个解法非常的精简, 而且我仔细看了之后, 我感觉这个解法的核心思想其实跟我这个closest pair的想法是类似的; 只不过他省略了很多其他的过程, 直接就针对问题本身用closest pair的逻辑来处理, 而没有我这个转化的过程;

仔细想想这个问题其实并没有我想的这么复杂. 我当时想的时候, 脑子里就是卡死在我们只能保存一个词的历史信息, 然后另外一个key用来作为current entry的判断什么的;

但是这个题目实际上你保存两个历史信息就行了: 分别保存两个key的历史信息:

这个题目的笨办法就是, 假如我们知道所有的两个key的分别的所有的index, 那么我们会怎么做? 其实就是我现在做的这个版本;
优化: 我们有必要知道所有的index吗? 众所周知, min/max的遍历问题, 是最不需要保存太多信息的, 经常O(1)的空间就能做出来了;

这个题目其实如果visual一下是更好解的: 不是visual一个words, 而是两个, 平行的, 然后distance就更容易看出来了;

另外注意他这里对于key相等的情况的处理, 非常的elegant: i1这个指针两用;

其实感觉在家里刷题也不是特别不好; 因为在家里状态不好, 所以经常想到各种笨办法. 就算最后没有一个想到一个笨办法的代码, 但是最起码这些对这些笨办法的探索对于最后理解最优解有非常大的帮助;

另外这个是Stefan稍微加速了之后的一个版本:

Same as solution 1, but minimizing the number of string comparisons.

public int shortestWordDistance(String[] words, String word1, String word2) {  
    long dist = Integer.MAX_VALUE, i1 = dist, i2 = -dist;  
    boolean same = word1.equals(word2);  
    for (int i=0; i<words.length; i++) {  
        if (words[i].equals(word1)) {  
            if (same) {  
                i1 = i2;  
                i2 = i;  
            } else {  
                i1 = i;  
            }  
        } else if (words[i].equals(word2)) {  
            i2 = i;  
        }  
        dist = Math.min(dist, Math.abs(i1 - i2));  
    }  
    return (int) dist;  
}

这个其实也没有很快, 4ms. 我后来加了一个优化, 跳掉所有的不等于either key的iteration(这样最后dist的更新就被跳掉了), 但是并没有实现加速;

他这两个算法对于i1和i2的初始化好像有点讲究? 但是没看出来到底什么门道? 难道是故弄玄虚?

这个是Stefan的帖子下面有个人写的一个简化版本:

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

这个非常的快, 2ms;

我当时自己想的时候, 有一个类似的想法, 因为所谓历史信息流, 你就要考虑到底使用word2找word1还是反过来? 能不能只判断either of the two keys, 但是不用管具体是哪一个?

他这里用的就是类似的这个的一个做法, j始终保存previous i. 整体的逻辑还是比较直白的: 一旦命中当中的一个: 我们直接判断当前的这个i跟j的两个word不相等的话, 那么这个distance就可以用来更新min(当然, 如果两个key相等的情况处理的方式就不同);

总体来说就是对Stefan的逻辑的一个简化, 不过不知道为什么稍微简化一下速度降低了这么多; 注意他这里i和j的关系, 其实j就是一个类似prev的作用; 这个方法的巧妙的一点在于, 你想想j到底是怎么定义的: the last i that we hit EITHER word1 or word2. 这样一个prev其实是不那么trivial的; 但是这样一个prev是否能够适用于我们这个问题? 并不一定, 我们要找到相邻的两个either hit的位置还不够, 我们还要确保这两个either hit不相等;

所以这个思路其实更像是找到所有相邻的word1 hit and word2 hit. 要确保相邻的这两个不相等. 实际实现的时候未必需要这么细分, 直接就判断either hit, 然后确保两者相等的情况无法更新min就行了;

有人对这个算法给出了一个优化:

Small improvements that can be made.

String equals are expensive task. No need to do equals of word1 and word2 in the loop. It can be computed just once and used as flag.

if (index != -1 && (word1.equals(word2) || !words[index].equals(words[i])))  
//Instead below can be used  
if (index != -1 && (sameWordsFlag || !words[index].equals(words[i])))

Instead of paying for so many equals, can track index of word1 and word2 separately, that will reduce the equals to just below. Of course the overall runtime remains the same and code will not be as compact as above but faster in practice for really long words.

if (words[i].equals(word1) || words[i].equals(word2))

是这个道理, 不过我感觉他说的这个就是Stefan的解法? 但是也是搞不懂, Stefan的解法其实并没有比这个快. 而且这个代码还compact很多;

另外一个版本:

public int shortestWordDistance(String[] words, String word1, String word2) {  
    if (words == null || words.length == 0) return 0;  
    int i1 = -words.length;  //here is to guarantee mindistance will be greater than the word.length  
    int i2 = words.length;  
    int min = Integer.MAX_VALUE;  
    for (int i = 0; i < words.length; i++) {  
        if (!word1.equals(word2)) {  
            if (words[i].equals(word1)) i1 = i;  
            if (words[i].equals(word2)) i2 = i;  
            min = Math.min(min, Math.abs(i1 - i2)); //so we don't have to check if (i1 != -1 && i2 != -1 in other solutions)  
        } else {  
            if (words[i].equals(word1)) {  //this the question on how to find the shortest distance of indices of the word  
                min = Math.min(min, Math.abs(i - i1));  //you can change to i - i1, it is also correct  
                i1 = i;  // update the i1 with current i for incoming distance checking  
            }  
        }  
    }  
    return min;  
}

其实核心思想是一样的, 只不过是把key相等和不相等的情况分开写了;

他这里关于i1和i2的初始化给出了解释, 这个不错;

这个算法最后还挺快的, 2ms;

word1 != word2 , it is simple, some are using i1 = -1, i2 = -1 to check, here I used the distance. Because when checking the min distance, I dont want fake min distance in my result, so I try to expand the initial distance of i1 and i2 be greater than words.length, (but we also cannot use i1 = -1 and i2 = words.length, because the target word might give i2 = 0, then mindistance is 1, which is also fake)
word1 == word2, the question becomes how to find the min distance of the indices of a single word. Such as "make" has indices of 0, 3, 5,xxxxx...how to find the min distance. Just use use current i minus last index and keep the global min value.

代码逻辑本身总体比较简练, 是一个好解法;

submission最优解: 1(96):

public class Solution {  
    public int shortestWordDistance(String[] words, String word1, String word2) {  
        int minDiff = Integer.MAX_VALUE,p1 = 0,p2 = 0;  
        if(word1.equals(word2)){  
            while(!words[p1].equals(word1)) ++p1;  
            int prev = p1++;  
            while(true){  
                while(p1<words.length&&!words[p1].equals(word1)) ++p1;  
                if(p1==words.length) return minDiff;  
                minDiff = Math.min(minDiff,p1-prev);  
                prev = p1++;  
            }  
        }else{  
            p1 = p2 = -words.length;  
            for(int i=0;i<words.length;i++){  
                if(words[i].equals(word1))  
                    minDiff = Math.min(minDiff,(p1=i)-p2);  
                else if(words[i].equals(word2))  
                    minDiff = Math.min(minDiff,(p2=i)-p1);  
            }  
        }  
        return minDiff;  
    }  
}

其实内部逻辑感觉还是差不多;

我这个题目还是想的太复杂了. 不知道他们这些人想出这个解法背后到底是什么动机? 或者就是一个iterate的本能? 管尼玛要找的是一个key还是两个key, 就是iterate;

无论如何, 这种shortest distance的题目, 也是要见过并且学习一下了;

Problem Description

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

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

word1 and word2 may be the same and they represent two individual words in the list.

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

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

Note:
You may assume word1 and word2 are both in the list.

Difficulty:Medium
Total Accepted:20.4K
Total Submissions:40.7K
Contributor: LeetCode
Companies
linkedin
Related Topics
array
Similar Questions
Shortest Word Distance Shortest Word Distance II

LC245 ShortestWordDistanceIII

ShortestWordDistanceIII [source code]

Problem Description

results matching ""

No results matching ""