AlgorithmJourney/LeetCode/LeetCode127.java at main · HenryJi529/AlgorithmJourney · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;

public class LeetCode127 {

    public static void main(String[] args) {
        // 输入：beginWord = "hit", endWord = "cog", wordList =
        // ["hot","dot","dog","lot","log","cog"]
        // 输出：5
        System.out.println(new Solution127_2().ladderLength("hit", "cog",
                Arrays.asList("hot", "dot", "dog", "lot", "log", "cog")));

        // 输入：beginWord = "hit", endWord = "cog", wordList =
        // ["hot","dot","dog","lot","log"]
        // 输出：0
        System.out.println(new Solution127_2().ladderLength("hit", "cog",
                Arrays.asList("hot", "dot", "dog", "lot", "log")));
    }
}

class Solution127_1 {
    // 复杂度为O(n^4)，不可行
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        Queue<String> queue = new LinkedList<String>();
        HashSet<String> visited = new HashSet<String>();
        queue.add(beginWord);
        int length = 1;
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                String cur = queue.poll();
                if (cur == endWord) {
                    return length;
                }
                for (String word : wordList) {
                    if (!visited.contains(word) && similar(word, cur)) {
                        queue.offer(word);
                    }
                }
            }
            length++;
        }
        return 0;
    }

    public boolean similar(String str1, String str2) {
        int length = str1.length();
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (str1.charAt(i) == str2.charAt(i)) {
                count++;
            }
        }
        return count == length - 1;
    }
}

class Solution127_2 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        HashMap<String, List<String>> graph = buildGraph(beginWord, wordList);
        Queue<String> queue = new LinkedList<>();
        HashSet<String> visited = new HashSet<String>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int length = 1;
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) {
                    return length;
                }
                for (String neighbor : graph.get(word)) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            length++;
        }
        return 0;
    }

    public HashMap<String, List<String>> buildGraph(String beginWord, List<String> wordList) {
        HashMap<String, List<String>> graph = new HashMap<String, List<String>>();
        for (String word : wordList) {
            graph.put(word, new ArrayList<String>());
        }
        for (int i = 0; i < wordList.size(); i++) {
            for (int j = i + 1; j < wordList.size(); j++) {
                if (similar(wordList.get(i), wordList.get(j))) {
                    graph.get(wordList.get(i)).add(wordList.get(j));
                    graph.get(wordList.get(j)).add(wordList.get(i));
                }
            }
        }
        graph.put(beginWord, new ArrayList<String>());
        for (String word : wordList) {
            if (similar(beginWord, word)) {
                graph.get(beginWord).add(word);
                graph.get(word).add(beginWord);
            }
        }
        return graph;
    }

    public boolean similar(String str1, String str2) {
        int length = str1.length();
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (str1.charAt(i) == str2.charAt(i)) {
                count++;
            }
        }
        return count == length - 1;
    }
}