Word Ladder

Question

1. 区分endWord是否要在dict里
2. dict给的是Set还是List
3. dict是否需要保持untouched

这里以leetcode为准

Solution

• 对每一层的所有可能words，都要进行检测。检测的时候，遍历word的每一个字符，对每一个字符要跟26个字母遍历比较一次，如果遇到可以构成的新的词，那么加入到下一层中，并且从字典中移除
• List需要进行contains,remove等操作的时候转化成set来做
  • List.contains/remove O(n)
  • Set.contains/remove O(1)
  • new HashSet(list)
• 注意这是一个求层数的问题，提前取queue的size
• 处理String中第i个字符的替换问题

  char[] array = str.toCharArray();
  array[i] = 'x';
  String newStr = String.valueOf(array);
  

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) return 0;
        HashSet<String> set = new HashSet<>();
        for (String str : wordList) {
            set.add(str);
        }
        Queue<String> queue = new LinkedList<String>();

        queue.offer(beginWord);
        int length = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            length++;
            for (int j = 0; j < size; j++) {
                String word = queue.poll();

                if (endWord.equals(word)) return length;

                for (int i = 0; i < word.length(); i++) {
                    //loop every char
                    for (char c = 'a'; c <= 'z'; c++) {

                        if (c == word.charAt(i)) {
                            continue;
                        }
                        char[] newWord = word.toCharArray();
                        newWord[i] = c;
                        String newStr = String.valueOf(newWord);

                        if (set.contains(newStr)) {
                            queue.offer(newStr);
                            set.remove(newStr);
                        }
                    }
                }
            }

        }

        return 0;
    }  
}

//DFS

Word Ladder II

• BFS + DFS