单词搜索 II

/*
 * Java Stream API is not suitable for DFS/BFS operations as it's more suitable
 * for functional-style operations on collections. However, we will use streams
 * to collect the results at the end.
 */
import java.util.*;
import java.util.stream.Collectors;
 
public class Solution {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    private boolean[][] visited;
 
    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        Set<String> result = new HashSet<>();
        TrieNode root = buildTrie(words);
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, result);
            }
        }
        // Using Java Stream API to convert Set to List
        return result.stream().collect(Collectors.toList());
    }
 
    private void dfs(char[][] board, int i, int j, TrieNode node, Set<String> result) {
        char c = board[i][j];
        if (c == '#' || node.next[c - 'a'] == null) return;
        node = node.next[c - 'a'];
        if (node.word != null) {   // Found a word
            result.add(node.word);
            node.word = null;   // Avoid duplicate results
        }
        board[i][j] = '#';   // Mark as visited
        for (int[] dir : DIRECTIONS) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && y >= 0 && x < m && y < n) {
                dfs(board, x, y, node, result);
            }
        }
        board[i][j] = c;   // Restore original character
    }
 
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.next[index] == null) node.next[index] = new TrieNode();
                node = node.next[index];
            }
            node.word = word;
        }
        return root;
    }
 
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
}