LeetCode link

first thought

  • same as bfs maze problem.
  • build a map to record the distance of each word.

solution

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
public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> map = new HashMap<>();
        for (String word: wordList) {
            map.put(word, Integer.MAX_VALUE);
        }
        Queue<String> queue = new LinkedList<>();
        map.put(beginWord, 1);
        queue.add(beginWord);
        while (!queue.isEmpty()) {
            String str = queue.poll();
            int dis = map.get(str);
            for (int i = 0; i < str.length(); i++) {
                StringBuilder builder = new StringBuilder(str);
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == str.charAt(i)) {
                        continue;
                    }
                    builder.setCharAt(i, c);
                    String newStr = builder.toString();
                    if (map.containsKey(newStr) && map.get(newStr) > dis + 1) {
                        map.put(newStr, dis + 1);
                        if (!endWord.equals(newStr)) {
                            queue.add(newStr);
                        }
                    }
                }
            }
        }
        return map.get(endWord) == Integer.MAX_VALUE ? 0 : map.get(endWord);
    }
}

problem

NPE

reason

in the return statement, remember the map may not contains the endWord

modification

check null in the return statement

1
return (map.get(endWord) == null || map.get(endWord) == Integer.MAX_VALUE) ? 0 : map.get(endWord);