首页 > itarticle > algorithm notes: leetcode#243 shortest word distance

algorithm notes: leetcode#243 shortest word distance

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        ans = len(words)
        idx = [-1, -1]
        
        for i, word in enumerate(words):
            if word == word1:
                idx[0] = i
            if word == word2:
                idx[1] = i
            if idx[0] != -1 and idx[1] != -1:
                ans = min(ans, abs(idx[1] - idx[0]))
    
        return ans

Java implementation

class  {
    public int shortestDistance(String[] words, String word1, String word2) {
        int ans = words.length;
        int[] idx = {-1, -1};
        
        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)){
                idx[0] = i;
            }
            if(words[i].equals(word2)){
                idx[1] = i;
            }
            if(idx[0] != -1 && idx[1] != -1){
                int curDist = Math.abs(idx[0] - idx[1]);
                ans = ans > curDist ? curDist : ans;
            }
        }
        return ans;
    }
}

Time complexity

O(N).

Space complexity

O(1).

Link

243. Shortest Word Distance