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
| class WordDistance {
private Map<String, List<Integer>> stringIdx;
public WordDistance(String[] wordsDict) {
stringIdx = new HashMap<>();
for (int i = 0; i < wordsDict.length; i++) {
stringIdx.putIfAbsent(wordsDict[i], new ArrayList<>());
stringIdx.get(wordsDict[i]).add(i);
}
}
public int shortest(String word1, String word2) {
List<Integer> word1List = stringIdx.get(word1);
List<Integer> word2List = stringIdx.get(word2);
int ptrOne = 0, ptrTwo = 0, ans = Integer.MAX_VALUE;
while (ptrOne < word1List.size() && ptrTwo < word2List.size()) {
int currDiff = Math.abs(word1List.get(ptrOne) - word2List.get(ptrTwo));
ans = Math.min(ans, currDiff);
if (word1List.get(ptrOne) < word2List.get(ptrTwo)) {
ptrOne += 1;
} else {
ptrTwo += 1;
}
}
return ans;
}
}
|
用map存每个word出现的index是哪些. 然后双指针解决即可.
时间复杂度: constructor是O(n) n是string array的长度. shortest是O(n). n是string array的长度, 因为可能string array中就两种string而且二者的频率是一样的. 这样的话就要遍历所有的index.
空间复杂度: O(n) map存所有string的index.
