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

# [interview] 244. Shortest Word Distance II

• mingki 작성
• 작성일

• 190 조회
• 2 댓글

### 본문

Medium

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님의 댓글

• 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>());
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;
}
}``````
전체 126 / 1 페이지

• 등록일 13:55
• 등록일 13:17
• 등록일 11:20
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23

### 새댓글

• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20
• 등록자 학부유학생 등록일 06.19
• 등록자 학부유학생 등록일 06.19

### Stats

• 현재 접속자 82 명
• 오늘 방문자 624 명
• 어제 방문자 683 명
• 최대 방문자 1,262 명
• 전체 회원수 264 명