按照老师的代码做了一遍,有个case没过,后来发现是wordList中存在一个word与beginWord相同,导致beginWord的编号不为0。
解决办法是手动put(beginWord, 0);然后ac了
不知这样做是否正确,请赐教
class Solution {
HashMap<String, Integer> dist;
Queue<String> q; // 广度优先
List<List<String>> ans;
List<String> path;
String beginWord;
HashSet<String> s;
public List<List<String>> findLadders(String _beginWord, String endWord, List<String> wordList) {
dist = new HashMap<>();
q = new LinkedList<>();
ans = new ArrayList<>();
path = new ArrayList<>();
s = new HashSet<>();
for (String word : wordList) {
s.add(word);
}
beginWord = _beginWord;
dist.put(beginWord, 0);
q.add(beginWord);
while(q.size() > 0) {
String r = q.poll();
StringBuilder t;
for (int i = 0; i < r.length(); i++) {
// 枚举当前的单词可以变成哪些单词(仅变换一个字符时)
t = new StringBuilder(r);
for (char j = 'a'; j <= 'z'; j++) {
if (j != r.charAt(i)) {
t.setCharAt(i, j);
String _t = t.toString();
if (s.contains(_t) && dist.getOrDefault(_t, 0) == 0) {
dist.put(_t, dist.get(r) + 1);
if (_t.equals(endWord)) {
break;
}
q.add(_t);
}
}
}
}
}
HashMap<String, Integer> test = dist;
dist.put(beginWord, 0);
if (dist.getOrDefault(endWord, 0) == 0) {
return ans;
}
path.add(endWord);
dfs(endWord);
return ans;
}
void dfs (String _t) {
// System.out.println(_t);
// for (int i = 0; i < path.size(); i++) {
// System.out.print(path.get(i) + " ");
// }
// System.out.println ();
if (_t.equals(beginWord)) {
List<String> line = new ArrayList<>();
for (int i = path.size()-1; i >= 0; i--) {
line.add(path.get(i));
}
ans.add(line);
// ans.add(path);
} else {
for (int i = 0; i < _t.length(); i++) {
StringBuilder t = new StringBuilder(_t);
for (char j = 'a'; j <= 'z'; j++) {
t.setCharAt(i, j);
String __t = t.toString();
if (dist.containsKey(__t) && dist.get(__t) + 1 == dist.getOrDefault(_t, 0)) {
// in a reverse order
// has a path to new t
path.add(__t);
dfs(__t);
path.remove(path.size() - 1);
}
}
}
}
}
}