Ming
0%

LeetCode-127

Posted on Edited on In

题目

结果

代码

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
class Solution {
    private final Set<String> visited = new HashSet<>();

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!contain(endWord, wordList) || beginWord.equals(endWord)) {
            return 0;
        }
        visited.add(beginWord);
        return bfs(branches(beginWord, wordList), endWord, wordList, 2);
    }

    private int bfs(List<String> branches, String endWord, List<String> wordList, int level) {
        // if the target is in this level
        if (branches.contains(endWord)) {
            return level;
        }

        Set<String> nextLevel = new HashSet<>();
        for (String branch : branches) {
            visited.add(branch);
            nextLevel.addAll(branches(branch, wordList));
        }

        // it seems that you can never reach the destination
        if (nextLevel.isEmpty()) {
            return 0;
        }
        return bfs(new LinkedList<>(nextLevel), endWord, wordList, level + 1);
    }

    // If wordList does not have the target word
    private boolean contain(String endWord, List<String> wordList) {
        for (String word : wordList) {
            if (word.equals(endWord)) {
                return true;
            }
        }
        return false;
    }

    // show me the way forward
    private List<String> branches(String beginWord, List<String> wordList) {
        Set<String> branches = new HashSet<>();
        for (String word : wordList) {
            // I can't make same mistakes once again
            if (!visited.contains(word) && changeable(beginWord, word)) {
                branches.add(word);
            }
        }
        return new LinkedList<>(branches);
    }

    // whether it can be done in one step
    private boolean changeable(String beginWord, String word) {
        int difference = 0;
        for (int i = 0; i < word.length(); i++) {
            if (difference > 1) {
                return false;
            }
            if (beginWord.charAt(i) != word.charAt(i)) {
                difference++;
            }
        }
        return difference == 1;
    }
}

复杂度

不好算啊