单词接龙

/*
  * 思路：
  * 1. 使用BFS和Java Stream处理数据。
  * 2. 将wordList转换为Set以便快速查找。
  * 3. 使用队列进行层级遍历，逐层检查可能的单词。
  * 4. 使用流式处理生成可能的新单词，并过滤已访问的单词。
  * 5. 如果找到endWord，返回层级；否则返回0。
  */
import java.util.*;
import java.util.stream.*;
 
public class SolutionStream {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
 
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 1;
 
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char originalChar = chars[j];
                    chars[j] = '*';
                    String pattern = new String(chars);
                    List<String> newWords = wordSet.stream()
                        .filter(w -> matches(pattern, w))
                        .collect(Collectors.toList());
                    for (String newWord : newWords) {
                        if (newWord.equals(endWord)) return level + 1;
                        queue.offer(newWord);
                        wordSet.remove(newWord);
                    }
                    chars[j] = originalChar;
                }
            }
            level++;
        }
 
        return 0;
    }
 
    private boolean matches(String pattern, String word) {
        if (pattern.length() != word.length()) return false;
        for (int i = 0; i < pattern.length(); i++) {
            if (pattern.charAt(i) != '*' && pattern.charAt(i) != word.charAt(i))
                return false;
        }
        return true;
    }
}