LeetCode212——单词搜索II

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/word-search-ii/description/

题目描述：

知识点：回溯、Trie

思路一：LeetCode079——单词搜索的加强版

时间复杂度是O(s)，其中s为words数组中的字符总数。空间复杂度是O(mn)，其中m为board数组的行数，n为board数组的列数。

JAVA代码：

public class Solution {
    boolean[][] flag;
    int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private boolean exist(char[][] board, String word) {
        int m = board.length;
        if(m == 0){
            return word.length() == 0;
        }
        int n = board[0].length;
        flag = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == word.charAt(0)){
                    flag[i][j] = true;
                    if(exist(board, word, 1, i, j)){
                        return true;
                    }
                    flag[i][j] = false;
                }
            }
        }
        return false;
    }
    //We have found [0, index] of word in board, trying to find index + 1.
    //Now we are in (x, y)
    private boolean exist(char[][] board, String word, int index, int x, int y){
        if(index == word.length()){
            return true;
        }
        for (int i = 0; i < directions.length; i++) {
            int newX = x + directions[i][0];
            int newY = y + directions[i][1];
            if(newX >=0 && newX < board.length && newY >= 0 && newY < board[0].length){
                if(!flag[newX][newY] && board[newX][newY] == word.charAt(index)){
                    flag[newX][newY] = true;
                    if(exist(board, word, index + 1, newX, newY)){
                        return true;
                    }
                    flag[newX][newY] = false;
                }
            }
        }
        return false;
    }
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> result = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            if(exist(board, words[i])){
                result.add(words[i]);
            }
        }
        return new ArrayList<>(result);
    }
}

LeetCode解题报告：

思路二：用Trie进行优化

首先将words数组中的单词存储进一个Trie数据结构中，再进行回溯寻找。

时间复杂度和空间复杂度与所给的words数组中的单词有关。

JAVA代码：

public class Solution {
    List<String> result = new ArrayList<>();
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode trieNode = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs (board, i, j, trieNode);
            }
        }
        return result;
    }
    public void dfs(char[][] board, int i, int j, TrieNode trieNode) {
        char c = board[i][j];
        if ('#' == c || null == trieNode.next[c - 'a']) return;
        trieNode = trieNode.next[c - 'a'];
        if (null != trieNode.word) {
            result.add(trieNode.word);
            trieNode.word = null;     //去重
        }
        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j ,trieNode);
        if (j > 0) dfs(board, i, j - 1, trieNode);
        if (i < board.length - 1) dfs(board, i + 1, j, trieNode);
        if (j < board[0].length - 1) dfs(board, i, j + 1, trieNode);
        board[i][j] = c;
    }
    private class TrieNode {
        private TrieNode[] next = new TrieNode[26];
        private String word;
    }
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode trieNode = root;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (null == trieNode.next[i]) {
                    trieNode.next[i] = new TrieNode();
                }
                trieNode = trieNode.next[i];
            }
            trieNode.word = word;
        }
        return root;
    }
}

LeetCode解题报告：