IVN
0%

Shortest Word Distance

Posted on Edited on In
Symbols count in article: 2.3k Reading time ≈ 2 mins.

Shortest Word Distance

243. Shortest Word Distance

法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int shortestDistance(String[] wordsDict, String word1, String word2) {
    int n= wordsDict.length;
    List<Integer> list1=new ArrayList<>();
    List<Integer> list2=new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if(wordsDict[i].equals(word1)){
            list1.add(i);
        }else if(wordsDict[i].equals(word2)){
            list2.add(i);
        }
    }
    int res=Integer.MAX_VALUE;
    for (Integer a : list1) {
        for (Integer b : list2) {
            res=Math.min(res,Math.abs(a-b));
        }
    }
    return res;
}

法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

244. Shortest Word Distance II

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
class WordDistance {

    HashMap<String, List<Integer>> map;
    HashMap<String,Integer> res;

    public WordDistance(String[] wordsDict) {
        map=new HashMap<>();
        res=new HashMap<>();
        int n= wordsDict.length;
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(wordsDict[i],new ArrayList<>());
            map.get(wordsDict[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        if(res.containsKey(word1+","+word2)){
            return res.get(word1+","+word2);
        }
        if(res.containsKey(word2+","+word1)){
            return res.get(word2+","+word1);
        }
        List<Integer> list1=map.get(word1);
        List<Integer> list2=map.get(word2);
        int min=Integer.MAX_VALUE;
        for (Integer a : list1) {
            for (Integer b : list2) {
                min=Math.min(min,Math.abs(a-b));
            }
        }
        res.put(word1+","+word2,min);
        return min;
    }
}

245. Shortest Word Distance III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
    int n=wordsDict.length;
    int res=Integer.MAX_VALUE;
    int index=-1;
    for (int i = 0; i < n; i++) {
        if (wordsDict[i].equals(word1) || wordsDict[i].equals(word2)) {
            if(index!=-1 && (word1.equals(word2) || !wordsDict[index].equals(wordsDict[i]))){
                res=Math.min(res,i-index);
            }
            index=i;
        }
    }
    return res;
}