FilesExpand file tree

 master

/

WordLadderII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

105 lines (91 loc) · 3.42 KB

 master

/

WordLadderII.java

Copy path

Top

File metadata and controls

• Code
• Blame

105 lines (91 loc) · 3.42 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.*;

/**

* TestCases

* "a", "c", ["a", "b", "c"]

* "hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]

* "hit", "cog", ["hot","hit","cog","dot","dog"]

* "red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]

*/

public class WordLadderII {

/**

* 这题核心就是保存前驱节点

*/

/**

* 保存前驱节点

*/

class WordNode {

String word;

WordNode prev;

public WordNode(String word, WordNode pre) {

this.word = word;

this.prev = pre;

}

}

public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {

List<List<String>> result = new ArrayList<List<String>>();

LinkedList<WordNode> next = new LinkedList<>();

LinkedList<WordNode> queue = new LinkedList<WordNode>();

queue.add(new WordNode(beginWord, null));

// 假如dict中有start则删掉

wordList.remove(beginWord);

wordList.add(endWord);

HashSet<String> visited = new HashSet<String>();

while (!queue.isEmpty()) {

WordNode top = queue.poll();

String word = top.word;

if (word.equals(endWord)) {

ArrayList<String> t = new ArrayList<String>();

for (WordNode p = top; p != null; p = p.prev) {

/**

* 注意这里是逆序添加

*/

t.add(0, p.word);

}

result.add(t);

/**

* 这里continue了，继续查看本层其它节点

*/

continue;

}

/**

* 这里非常关键，result非空表示已经找到了一条最短路径，则当前层就是最短的了，给当前层遍历完毕就OK了

* 而queue是空则表示当前层已经遍历完毕了

*/

if (!result.isEmpty() && queue.isEmpty()) {

break;

}

/**

* 这里可以优化一下，如果wordList为空，则这个for循环是没有意义的

*/

StringBuilder sb = new StringBuilder(word);

for (int i = 0; i < word.length(); i++) {

char c = word.charAt(i);

for (int j = 0; j < 26; j++) {

if ('a' + j == c) {

continue;

}

sb.setCharAt(i, (char) ('a' + j));

String newWord = sb.toString();

if (wordList.contains(newWord)) {

/**

* 这里同一个单词可能会重复添加，对应着多条路径

*/

next.add(new WordNode(newWord, top));

visited.add(newWord);

}

}

sb.setCharAt(i, c);

}

if (queue.isEmpty()) {

queue.addAll(next);

next.clear();

/**

* 只有本层都走完了才能将访问过的word从dict中删除，因为同一层同一个单词可能会被多次利用

* 比如上一层的dot和hog都能对应到本层的hot，那么hot就要重复利用，对应着两条路径

*/

wordList.removeAll(visited);

}

}

return result;

}

}