Shortest Word Distance

题目

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"].

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

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

分析

1. two pointers: a, b
2. it starts at the left end and scans through to the right end of String array
3. if word1 is found in String array, assign current index value to a; if word2 is found, assign current index value to b
4. keep track of Math.abs(a-b)
5. result is either previous result, or Math.abs(a-b), whichever is smaller

图解

解题

//time : o(n) 
//space: o(1)
class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int result = Integer.MAX_VALUE;
        int a = -1;
        int b = -1;
        for(int i = 0; i< words.length; i++){
            if(words[i].equals(word1)){
                a = i;
            }else if(words[i].equals(word2)){
                b = i;
            }
            if(a!=-1 && b !=-1){
            result = Math.min(result, Math.abs(a-b));
            }       
        }
        return result;
    }
}