题目描述(困难难度)

79 题 Word Search 的延续。

意思就是从某个字符出发,然后它可以向左向右向上向下移动,走过的路径构成一个字符串,判断是否能走出给定字符串的 word ,还有一个条件就是走过的字符不能够走第二次。

比如 eat,从第二行最后一列的 e 出发,向左移动,再向左移动,就走出了 eat。

题目中给一个 word 列表,要求找出哪些单词可以由 board 生成。

解法一

直接利用 79 题 的代码 ,79 题是判断某个单词能否在 board 中生成。这里的话,很简单,直接遍历 words 数组,然后利用 79 题的代码去依次判断即可。

79 题 使用的时候采用 dfs ,没做过的话大家可以先过去看一下。

public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();
    //判断每个单词
    for (String word : words) {
        if (exist(board, word)) {
            res.add(word);
        }
    }
    return res;
}
//下边是 79 题的代码
public boolean exist(char[][] board, String word) {
    int rows = board.length;
    if (rows == 0) {
        return false;
    }
    int cols = board[0].length;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (existRecursive(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean existRecursive(char[][] board, int row, int col, String word, int index) {
    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
        return false;
    }
    if (board[row][col] != word.charAt(index)) {
        return false;
    }
    if (index == word.length() - 1) {
        return true;
    }
    char temp = board[row][col];
    board[row][col] = '$';
    boolean up = existRecursive(board, row - 1, col, word, index + 1);
    if (up) {
        board[row][col] = temp; //将 board 还原, 79 题中的代码没有还原,这里必须还原
        return true;
    }
    boolean down = existRecursive(board, row + 1, col, word, index + 1);
    if (down) {
        board[row][col] = temp;//将 board 还原, 79 题中的代码没有还原,这里必须还原
        return true;
    }
    boolean left = existRecursive(board, row, col - 1, word, index + 1);
    if (left) {
        board[row][col] = temp;//将 board 还原, 79 题中的代码没有还原,这里必须还原
        return true;
    }
    boolean right = existRecursive(board, row, col + 1, word, index + 1);
    if (right) {
        board[row][col] = temp;//将 board 还原, 79 题中的代码没有还原,这里必须还原
        return true;
    }
    board[row][col] = temp;
    return false;
}

然后它竟然过了,竟然过了。。。我还以为这么暴力一定会暗藏玄机。不过为了尊重它是一道 hard 的题目,我就继续思考能不能优化下。

顺着上边的思路想,首先 79 题 中判断单个单词是否能生成肯定不能优化了,不然之前肯定会写优化方法。那么继续优化的话,就只能去寻求不同 word 的之间的联系了。

什么意思呢?

就是如果知道了某个单词能生成,那么对于后边将要判断的单词能不能提供些帮助呢?

或者知道了某个单词不能生成,对于后边将要判断的单词能不能提供些帮助呢?

想了想,只想到了一种情况。比如我们已经知道了 basketboard 能够在二维数组 board 中生成。那么它的所有前缀一定也能生成,比如 basket 一定能够生成。

说到前缀,自然而然的想到了之前的前缀树,这几天出现的频率也比较高,刚做的 211 题 也用到了。我们可以把能生成的 word 加入到前缀树中,然后再判断后边的单词前,先判断它是不是前缀树中某个单词的前缀。

当然如果单词 AB 的前缀,那么 A 的长度肯定短一些,所以我们必须先判断了较长的单词 B,才能产生优化的效果。所以我们首先要把 words 按照单词的长度从大到小排序。

小弟不才,只想到了这一种联系,下边是代码,前缀树直接搬 208 题 的代码即可。

//208 题前缀树代码
class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean flag;

        public TrieNode() {
            children = new TrieNode[26];
            flag = false;
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            // 当前孩子是否存在
            if (cur.children[array[i] - 'a'] == null) {
                cur.children[array[i] - 'a'] = new TrieNode();
            }
            cur = cur.children[array[i] - 'a'];
        }
        // 当前节点代表结束
        cur.flag = true;
    }

    /**
         * Returns if there is any word in the trie that starts with the given
         * prefix.
         */
    public boolean startsWith(String prefix) {
        char[] array = prefix.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        return true;
    }

};
//本题代码
public List<String> findWords(char[][] board, String[] words) {
    //将单词的长度从大到小排序
    Arrays.sort(words, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.length() - o1.length();
        }

    });
    Trie trie = new Trie();
    List<String> res = new ArrayList<>();
    for (String word : words) {
        //判断当前单词是否是已经完成的单词的前缀
        if (trie.startsWith(word)) {
            res.add(word);
            continue;
        }
        if (exist(board, word)) {
            res.add(word);
            //加入到前缀树中
            trie.insert(word);
        }
    }
    return res;
}
//下边是 79 题的代码
public boolean exist(char[][] board, String word) {
    int rows = board.length;
    if (rows == 0) {
        return false;
    }
    int cols = board[0].length;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (existRecursive(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
}


private boolean existRecursive(char[][] board, int row, int col, String word, int index) {
    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
        return false;
    }
    if (board[row][col] != word.charAt(index)) {
        return false;
    }
    if (index == word.length() - 1) {
        return true;
    }
    char temp = board[row][col];
    board[row][col] = '$';
    boolean up = existRecursive(board, row - 1, col, word, index + 1);
    if (up) {
        board[row][col] = temp;
        return true;
    }
    boolean down = existRecursive(board, row + 1, col, word, index + 1);
    if (down) {
        board[row][col] = temp;
        return true;
    }
    boolean left = existRecursive(board, row, col - 1, word, index + 1);
    if (left) {
        board[row][col] = temp;
        return true;
    }
    boolean right = existRecursive(board, row, col + 1, word, index + 1);
    if (right) {
        board[row][col] = temp;
        return true;
    }
    board[row][col] = temp;
    return false;
}

然而事实是残酷的,对于 leetcodetest cases ,这个想法并没有带来速度上的提升。于是就去逛 discuss 了,也就是下边的解法二。

解法二

参考 这里)。

解法一中的想法是,从 words 中依次选定一个单词 -> 从图中的每个位置出发,看能否找到这个单词

我们其实可以倒过来。从图中的每个位置出发 -> 看遍历过程中是否遇到了 words 中的某个单词

遍历过程中判断是否遇到了某个单词,我们可以事先把所有单词存到前缀树中。这样的话,如果当前走的路径不是前缀树的前缀,我们就可以提前结束了。如果是前缀树的中的单词,我们就将其存到结果中。

至于实现的话,我们可以在遍历过程中,将当前路径的单词传进函数,然后判断当前路径构成的单词是否是在前缀树中出现即可。

这个想法可行,但不够好,因为每次都从前缀树中判断当前路径的单词,会带来重复的判断。比如先判断了 an 存在于前缀树中,接下来假如路径变成 ang ,判断它在不在前缀中,又需要判断一遍 an

因此,我们可以将前缀树融合到我们的算法中,递归中去传递前缀树的节点,判断当前节点的孩子是否为 null,如果是 null 说明当前前缀不存在,可以提前结束。如果不是 null,再判断当前节点是否是单词的结尾,如果是结尾直接将当前单词加入。

由于递归过程中没有加路径,所以我们改造一下前缀树的节点,将单词直接存入节点,这样的话就可以直接取到了。

干巴巴的文字可能不好理解,看一下下边的代码应该就明白了。

//改造前缀树节点
class TrieNode {
    public TrieNode[] children;
    public String word; //节点直接存当前的单词

    public TrieNode() {
        children = new TrieNode[26];
        word = null;
        for (int i = 0; i < 26; i++) {
            children[i] = null;
        }
    }
}
class Trie {
    TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            // 当前孩子是否存在
            if (cur.children[array[i] - 'a'] == null) {
                cur.children[array[i] - 'a'] = new TrieNode();
            }
            cur = cur.children[array[i] - 'a'];
        }
        // 当前节点结束,存入当前单词
        cur.word = word;
    }
};

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        //将所有单词存入前缀树中
        List<String> res = new ArrayList<>();
        for (String word : words) {
            trie.insert(word);
        }
        int rows = board.length;
        if (rows == 0) {
            return res;
        }
        int cols = board[0].length;
        //从每个位置开始遍历
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                existRecursive(board, i, j, trie.root, res);
            }
        }
        return res;
    }

    private void existRecursive(char[][] board, int row, int col, TrieNode node, List<String> res) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return;
        }
        char cur = board[row][col];//将要遍历的字母
        //当前节点遍历过或者将要遍历的字母在前缀树中不存在
        if (cur == '$' || node.children[cur - 'a'] == null) {
            return;
        }
        node = node.children[cur - 'a'];
        //判断当前节点是否是一个单词的结束
        if (node.word != null) {
            //加入到结果中
            res.add(node.word);
            //将当前单词置为 null,防止重复加入
            node.word = null;
        }
        char temp = board[row][col];
        //上下左右去遍历
        board[row][col] = '$';
        existRecursive(board, row - 1, col, node, res);
        existRecursive(board, row + 1, col, node, res);
        existRecursive(board, row, col - 1, node, res);
        existRecursive(board, row, col + 1, node, res);
        board[row][col] = temp;
    }
}

结合代码就很好懂了,就是从每个位置对图做深度优先搜索,然后路径生成的字符串如果没有在前缀树中出现就提前结束,如果到了前缀树中某个单词的结束,就将当前单词加入即可。

受到前边的题目思维的限制,只想到了解法一,优化的话也没有很成功。其实把思路倒过来,解法二也就可以出来了,很有意思。

results matching ""

    No results matching ""