1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
Map<String, List<Integer>> wordIndex = new HashMap<>();
for (int i = 0; i < wordsDict.length; i++) {
String word = wordsDict[i];
wordIndex.putIfAbsent(word, new ArrayList<>());
List<Integer> wordList = wordIndex.get(word);
if (wordList.size() == 0) {
wordList.add(Integer.MAX_VALUE);
wordList.add(i);
} else {
int distanceToLast = i - wordList.get(wordList.size() - 1);
wordList.set(0, Math.min(distanceToLast, wordList.get(0)));
wordList.add(i);
}
}
if (word1.equals(word2)) {
return wordIndex.get(word1).get(0);
} else {
List<Integer> word1List = wordIndex.get(word1);
List<Integer> word2List = wordIndex.get(word2);
int ptrOne = 1, ptrTwo = 1, ans = Integer.MAX_VALUE;
while (ptrOne < word1List.size() && ptrTwo < word2List.size()) {
int word1Index = word1List.get(ptrOne), word2Index = word2List.get(ptrTwo);
ans = Math.min(ans, Math.abs(word1Index - word2Index));
if (word1List.get(ptrOne) < word2List.get(ptrTwo)) {
ptrOne += 1;
} else {
ptrTwo += 1;
}
}
return ans;
}
}
}
|
最直接的想法. 用map存每个word出现的位置在哪里. 其中word对应的list存相同word的最短距离, 如果word只出现一次, 那么这个值就是Integer.MAX_VALUE.
如果两个word一样, 那好说, 就是对应list的第0个元素的值. 如果不一样, 我们把两个word对应的list拿出来, 然后双指针即可. 为什么双指针可以work? 因为如果一方大, 那么它之后的index和另一方构成的distance肯定比现在的大, 因此无需遍历, 我们增加另一方即可.
时间复杂度: O(n)
空间复杂度: O(n) 因为要存每个element的index进入map中.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
int index = -1, ans = Integer.MAX_VALUE;
String prevWord = null;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1) || wordsDict[i].equals(word2)) {
if (index != -1 && (word1.equals(word2) || !prevWord.equals(wordsDict[i]))) {
ans = Math.min(ans, i - index);
}
index = i;
prevWord = wordsDict[i];
}
}
return ans;
}
}
|
这个思路好. 就是存上一个word1或者word2的index. 如果word1和word2一样并且之前有它俩之一的word出现, 那么计算此时的距离并且和ans比较. 让ans等于小的值. 如果word1和word2不一样此时上一次出现的word和此时的word不能相同. 计算距离然后让ans等于较小的值. 我们可以用反证法证明如果word1和word2不一样, 那么挨着最近的一对之间一定没有word1或者word2出现, 否则这一对儿就不是最近的.
时间复杂度: O(n)
空间复杂度: O(1)
