[LeetCode] 212. Word Search II

Flands 發布于2019-08-16 13:40 / 3087人閱讀

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;
    }
}

云服務器 GPU云服務器 v212 LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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