05 August 2008
Array中找单词距离
HashMap用单词和位置当作KV
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
int result = words.length;
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String str = words[i];
if (str.equals(word1) && map.containsKey(word2)) {
result = Math.min(result, i - map.get(word2));
} else if (str.equals(word2) && map.containsKey(word1)) {
result = Math.min(result, i - map.get(word1));
}
map.put(str, i);
}
return result;
}
}
不用HashMap，O(m * n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
int index = -1;
int min = words.length;
for (int i = 0; i < words.length; i++) {
if (words[i].equals(word1) || words[i].equals(word2)) {
if (index != -1 && !words[index].equals(words[i])) {
min = Math.min(i - index, min);
}
index = i;
}
}
return min;
}
}