Java two cursor sliding window.


  • 0
    J
    	public int shortestDistance(String[] words, String word1, String word2) {
    	String nextWord = "";
    	int firstIndex = 0;
    	int n = words.length, minDistance = Integer.MAX_VALUE;
    	
    	//use two cursors, sliding window aglo.
    	int k = 0;
    	while (k < n) {
    		int i = k;
    		
    		//move to the first word
    		while (i < n && !words[i].equals(word1) && !words[i].equals(word2)) {
    			i++;
    		}
    		if (i < n) {
    			//found the first word.
    			nextWord = (words[i].equals(word1)) ? word2 : word1;
    			firstIndex = i;
    			k = firstIndex + 1;
    		} else { 
    			//i == n, first word not found. exit loop.
    			k = n;
    		}
    		
    		//move to the second word.
    		while (i < n && !words[i].equals(nextWord)) {
    			i++;
    		}
    		if (i < n) {
    			//found the second word, save the distance.
    			minDistance = Math.min(minDistance, i - firstIndex);
    		}
    	}
    	return minDistance;
    }

Log in to reply
 

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