Java 2ms sloution with 2 pointers and O(n) time complexity, O(1) Space


  • 0
    B

    Java 2 pointers solution with O(n) time complexity and O(1) space

    public int shortestDistance(String[] words, String word1, String word2) {
        if(words.length == 2) return 1;
    //index of first word (it could be word1 or word 2)  we see when sacnning array    
        int first =  0;     
    //the second word we see (if first word is word1, second should be word2; if first is word2, second should be word1)
        int second = 0;     
        int min = Integer.MAX_VALUE;
        
        while(!words[first].equals(word1) && !words[first].equals(word2))
            first++;
        
        for(second = first + 1; second < words.length; second++)
        {
            if(!words[second].equals(word1) && !words[second].equals(word2))
                ;
            else if(words[second].equals(words[first]))
                first = second;
            else
            {
                min = Math.min(min, second - first);
                first = second;
            }
        }
        return min;
    }

Log in to reply
 

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