[LeetCode] 212. Word Search II

Flands 发布于2019-08-16 13:40 / 2993人阅读

Problem

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
words = ["oath","pea","eat","rain"] and board =
[
  ["o","a","a","n"],
  ["e","t","a","e"],
  ["i","h","k","r"],
  ["i","f","l","v"]
]

Output: ["eat","oath"]

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }
    
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word: words) {
            TrieNode cur = root;
            for (char ch: word.toCharArray()) {
                int i = ch-"a";
                if (cur.children[i] == null) cur.children[i] = new TrieNode();
                cur = cur.children[i];
            }
            cur.word = word;
        }
        return root;
    }
    
    public List findWords(char[][] board, String[] words) {
        List res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
    
    private void dfs(char[][] board, int i, int j, TrieNode root, List res) {
        char ch = board[i][j];
        if (ch == "#" || root.children[ch-"a"] == null) return;
        
        root = root.children[ch-"a"];
        if (root.word != null) { //found one
            res.add(root.word);
            root.word = null; //de-dup
        }
        
        board[i][j] = "#";
        if (i > 0) dfs(board, i-1, j, root, res);
        if (j > 0) dfs(board, i, j-1, root, res);
        if (i < board.length-1) dfs(board, i+1, j, root, res);
        if (j < board[0].length-1) dfs(board, i, j+1, root, res);
        board[i][j] = ch;
    }
}

服务器托管私有云 v212 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72136.html

[Leetcode] Word Search I&II 二维字符矩阵查找单词

摘要：复杂度时间空间为长度，为大小空间复杂度是是因为我用存信息，只动态地存当前的路径如果用来存信息的话空间复杂度就是时间复杂度对每个点都要作为起始点，对于每个起始点，拓展一次有四个可能性四个邻居，要拓展次长度为。思路暴力搜索带走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...

LuDongWei 2019-08-14 14:06 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
[Leetcode] Word Search 单词搜索

摘要：我们可以先用待查单词建立一个字典树，这样我们在从矩阵中某个点开始深度优先搜索时，可以直接用字典树判断当前组成的字符串是否是某个单词的前缀。字典树同样也提供接口，所以同样可以用于判断是否已经搜索到这个词了。 Word Search I 更新的思路与解法请访问：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

objc94 2019-08-14 12:25 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0