Leetcode-word-ladder-ii

题目描述

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start =”hit”
end =”cog”
dict =[“hot”,”dot”,”dog”,”lot”,”log”]

Return

1
2
3
4
5
>   [
> ["hit","hot","dot","dog","cog"],
> ["hit","hot","lot","log","cog"]
> ]
>

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

首先说明,下面的代码是没有通过的,因为存在数组越界等非法访问情况,但是具体在哪里,又因为是什么原因我没有发现。我的解决思路是通过递归来实现。如果要a→b→c上的所有可能,那么就是a→b和b→c上的所有可能的组合。

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
import java.util.*;

public class Solution {

public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {

​ ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();

if (start.equals(end)) {

​ ArrayList<String> list = new ArrayList<String>();

​ list.add(end);

​ res.add(list);

return res;

​ }

​ HashSet<String> d = new HashSet<String>(dict);

​ Iterator iterator = dict.iterator();

while (iterator.hasNext()) {

​ String word = iterator.next().toString();

if (diff(start, word) == 1) {

​ d.remove(word);

​ ArrayList<ArrayList<String>> getRes = findLadders(word, end, dict);

if (getRes == null || getRes.size() == 0) {

continue;

​ }

for (ArrayList<String> eachRes : getRes) {

if (eachRes != null) {

if (eachRes.size() == 0) {

​ eachRes.add(start);

​ } else {

​ eachRes.add(0, start);

​ }

​ res.add(eachRes);

​ }

​ }

​ }

​ }

return res;

​ }

public int diff(String s1, String s2) {

int res = 0;

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

if (s1.charAt(i) != s2.charAt(i)) {

​ res++;

​ }

​ }

return res;

​ }

}