This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
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.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.
Note:
You may assume word1 and word2 are both in the list.
此题和之前的两道题区别是，可以word1 equals word2，我用的2的思想来做的，代码如下：
public class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
Map<String,List<Integer>> map = new HashMap<>();
for(int i=0;i<words.length;i++){
if(!map.containsKey(words[i])){
List<Integer> list = new ArrayList<Integer>();
map.put(words[i],list);
}
map.get(words[i]).add(i);
}
List<Integer> list1 = map.get(word1);
List<Integer> list2 = map.get(word2);
int min = Integer.MAX_VALUE;
if(list1==list2){
for(int i=0;i<list1.size()-1;i++){
min = Math.min(min,Math.abs(list1.get(i+1)-list1.get(i)));
}
}else{
for(int l1:list1){
for(int l2:list2){
min = Math.min(min,Math.abs(l1-l2));
}
}
}
return min;
}
}
看了答案，代码如下：
public class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
long dis = Integer.MAX_VALUE;
long p1 = dis;
long p2 = -dis;
boolean same = word1.equals(word2);
for(int i=0;i<words.length;i++){
if(words[i].equals(word1)){
if(same){
p1 = p2;
p2 = i;
}else{
p1 = i;
}
}else if(words[i].equals(word2)){
p2 = i;
}
dis = Math.min(dis,Math.abs(p1-p2));
}
return (int)dis;
}
}
这里面有一些细节需要注意，首先，long型定义。其次 long p2 = -dis;因为Math.abs(p1-p2)，如果p2为dis的话，那么Math.abs就是0了。此题的精妙之处在于p1 = p2;p2 = i;轮流赋值