엔지니어 게시판
LeetCode 솔루션 분류

[interview] 244. Shortest Word Distance II

컨텐츠 정보

본문

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.

관련자료

댓글 2

학부유학생님의 댓글

  • 익명
  • 작성일
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

Coffee님의 댓글

  • 익명
  • 작성일
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;
    }
}
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 169 명
  • 오늘 방문자 2,674 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,047 명
알림 0