这三道题差别不是非常大所以可以放在一起练习。
243. Shortest Word Distance
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Input: word1 =“coding”, word2 =“practice”Output: 3
Input: word1 ="makes", word2 ="coding"Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
题意是给一个words列表，请你返回其中两个单词word1和word2之间的下标差。这两个单词一定是不同的。
时间O(n)
空间O(1)
Java实现
1 class Solution {
2 public int shortestDistance(String[] words, String word1, String word2) {
3 int res = words.length;
4 int a = -1;
5 int b = -1;
6 for (int i = 0; i < words.length; i++) {
7 if (words[i].equals(word1)) {
8 a = i;
9 } else if (words[i].equals(word2)) {
10 b = i;
11 }
12 if (a != -1 && b != -1) {
13 res = Math.min(res, Math.abs(a - b));
14 }
15 }
16 return res;
17 }
18 }
244. Shortest Word Distance II
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. Your method will be called repeatedly many times with different parameters.
Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Input: word1 =“coding”, word2 =“practice”Output: 3
Input: word1 ="makes", word2 ="coding"Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
1 class WordDistance {
2 HashMap<String, List<Integer>> map;
3
4 public WordDistance(String[] words) {
5 map = new HashMap<>();
6 for (int i = 0; i < words.length; i++) {
7 if (map.containsKey(words[i])) {
8 map.get(words[i]).add(i);
9 } else {
10 map.put(words[i], new ArrayList<>());
11 map.get(words[i]).add(i);
12 }
13 }
14 }
15
16 public int shortest(String word1, String word2) {
17 List<Integer> l1 = map.get(word1);
18 List<Integer> l2 = map.get(word2);
19 int res = Integer.MAX_VALUE;
20 for (Integer num1 : l1) {
21 for (Integer num2 : l2) {
22 res = Math.min(res, Math.abs(num1 - num2));
23 }
24 }
25 return res;
26 }
27 }
28
29 /**
30 * Your WordDistance object will be instantiated and called as such:
31 * WordDistance obj = new WordDistance(words);
32 * int param_1 = obj.shortest(word1,word2);
33 */
245. Shortest Word Distance III
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Input: word1 =“makes”, word2 =“coding”Output: 1
Input: word1 ="makes", word2 ="makes"Output: 3
Note:
You may assume word1 and word2 are both in the list.
245题与前两题的区别在于word1和word2有可能是相同的。当然，如果他们相同的话，意味着这个单词出现了多次。还是找最短距离。
时间O(n)
空间O(1)
Java实现
1 class Solution {
2 public int shortestWordDistance(String[] words, String word1, String word2) {
3 int p1 = -1;
4 int p2 = -1;
5 int distance = words.length;
6 for (int i = 0; i < words.length; i++) {
7 if (words[i].equals(word1)) {
8 p1 = i;
9 if (p1 != -1 && p2 != -1) {
10 distance = (p1 != p2) ? Math.min(distance, Math.abs(p1 - p2)) : distance;
11 }
12 }
13 if (words[i].equals(word2)) {
14 p2 = i;
15 if (p1 != -1 && p2 != -1) {
16 distance = (p1 != p2) ? Math.min(distance, Math.abs(p1 - p2)) : distance;
17 }
18 }
19 }
20 return distance;
21 }
22 }