LeetCode 솔루션

[interview] 244. Shortest Word Distance II

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.06.16 21:25

7,097 조회
2 댓글
0 추천
0 비추천
목록

글검색

게시글 쓰기

Medium

877267Add to ListShare

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

Constraints:

1 <= wordsDict.length <= 3 * 104
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2
At most 5000 calls will be made to shortest.

#Linkedin, #Array, #Hash Table, #Two Pointers, #String, #Design

링크

https://leetcode.com/problems/shortest-word-distance-ii/ 977 회 연결

익명
작성일 2022.06.16 21:42

Runtime: 180 ms, faster than 21.25% of Python3 online submissions for Shortest Word Distance II.
Memory Usage: 22 MB, less than 8.88% of Python3 online submissions for Shortest Word Distance II.

class WordDistance:

    def __init__(self, wordsDict: List[str]):
        self.word_dict = collections.defaultdict(list)
        for idx, word in enumerate(wordsDict):
            self.word_dict[word].append(idx)

    def shortest(self, word1: str, word2: str) -> int:
        
        idx_list1, idx_list2 = self.word_dict[word1].copy(), self.word_dict[word2].copy()
        
        curr1, curr2 = idx_list1.pop(), idx_list2.pop()
        min_diff = abs(curr1-curr2)
        while idx_list1 or idx_list2:
            if idx_list1 and (not idx_list2 or curr1 > curr2):
                curr1 = idx_list1.pop()
            else:
                curr2 = idx_list2.pop()
            
            min_diff = min(min_diff, abs(curr1-curr2))
        
        return min_diff

익명
작성일 2022.06.20 17:59

class WordDistance {

    HashMap<String, ArrayList<Integer>> map;
    
    int min = Integer.MAX_VALUE;
    
    public WordDistance(String[] wordsDict) {
        
        this.map = new HashMap<String, ArrayList<Integer>>();
        for(int i=0; i<wordsDict.length; i++){
            ArrayList<Integer> wordPos = this.map.getOrDefault(wordsDict[i], new ArrayList<Integer>());
            wordPos.add(i);
            this.map.put(wordsDict[i], wordPos);
        }
    }
    
    public int shortest(String word1, String word2) {
        ArrayList<Integer> loc1, loc2;
        
        loc1 = this.map.get(word1);
        loc2 = this.map.get(word2);
        
        int minDiff = Integer.MAX_VALUE;
        int pos1 = 0, pos2 = 0;
        while(pos1 < loc1.size() && pos2 < loc2.size()){
            minDiff = Math.min(minDiff, Math.abs(loc1.get(pos1) - loc2.get(pos2)));
            if(loc1.get(pos1) < loc2.get(pos2)){
                pos1++;
            }else{
                pos2++;
            }
        }
        
        return minDiff;
    }
}

[code=java]class WordDistance {

HashMap<String, ArrayList<Integer>> map;
    
    int min = Integer.MAX_VALUE;
    
    public WordDistance(String[] wordsDict) {
        
        this.map = new HashMap<String, ArrayList<Integer>>();
        for(int i=0; i<wordsDict.length; i++){
            ArrayList<Integer> wordPos = this.map.getOrDefault(wordsDict[i], new ArrayList<Integer>());
            wordPos.add(i);
            this.map.put(wordsDict[i], wordPos);
        }
    }
    
    public int shortest(String word1, String word2) {
        ArrayList<Integer> loc1, loc2;
        
        loc1 = this.map.get(word1);
        loc2 = this.map.get(word2);
        
        int minDiff = Integer.MAX_VALUE;
        int pos1 = 0, pos2 = 0;
        while(pos1 < loc1.size() && pos2 < loc2.size()){
            minDiff = Math.min(minDiff, Math.abs(loc1.get(pos1) - loc2.get(pos2)));
            if(loc1.get(pos1) < loc2.get(pos2)){
                pos1++;
            }else{
                pos2++;
            }
        }
        
        return minDiff;
    }
}[/code]