Concise O(n) one-pass JAVA solution


  • 0

    p1, p2 is the last position of word1, word2, then we calculate the distance between the current word1(word2) with the previous word2(word1), output the shortest one.

    A little trick for this problem is to check if 'p1 != p2' to deal with the situation that word1 = word2.

    Time complexity = O(n)

    As we use one pass, so the time complexity is O(n).

    JAVA Code:

    public int shortestWordDistance(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 (p2 != - 1) min = Math.min(min, p1 - p2);
    		}			 
    		if (words[i].equals(word2)) {
    			p2 = i;
    			if (p1 != - 1 && p1 != p2) min = Math.min(min, p2 - p1);
    		}			
    	}		
    	return min;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.