成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Word Search 單詞搜索

objc94 / 2116人閱讀

摘要:我們可以先用待查單詞建立一個字典樹,這樣我們在從矩陣中某個點開始深度優(yōu)先搜索時,可以直接用字典樹判斷當前組成的字符串是否是某個單詞的前綴。字典樹同樣也提供接口,所以同樣可以用于判斷是否已經(jīng)搜索到這個詞了。

Word Search I 更新的思路與解法請訪問:https://yanjia.me/zh/2018/11/...

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

For example, Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

深度優(yōu)先搜索 復雜度

時間 O(N^2) 空間 O(N)

思路

基本思路很簡單,對矩陣里每個點都進行一次深度優(yōu)先搜索,看它能夠產(chǎn)生一個路徑和所給的字符串是一樣的。重點在如何優(yōu)化搜索,避免不必要的計算。比如我們一個方向的搜索中已經(jīng)發(fā)現(xiàn)了這個詞,那我們就不用再搜索。另外,為了避免循環(huán)搜索,我們還要將本輪深度優(yōu)先搜索中搜索過的數(shù)字變一下,等遞歸回來之后再變回來。實現(xiàn)這個特性最簡單的方法就是異或上一個特定數(shù),然后再異或回來。

代碼
public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length == 0) return false;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                // 從i,j點作為起點開始搜索
                boolean isExisted = search(board, i, j, word, 0);
                if(isExisted) return true;
            }
        }
        return false;
    }
    
    private boolean search(char[][] board, int i, int j, String word, int idx){
        if(idx >= word.length()) return true;
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)) return false;
        // 將已經(jīng)搜索過的字母標記一下,防止循環(huán)。只要變成另外一個字符,就不會再有循環(huán)了。
        board[i][j] ^= 255;
        boolean res = search(board, i-1, j, word, idx+1) || search(board, i+1, j, word, idx+1) || search(board, i, j-1, word, idx+1) || search(board, i, j+1, word, idx+1);
        // 再次異或255就能恢復成原來的字母
        board[i][j] ^= 255;
        return res;
    }
}
Word Search II

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.

For example, Given words = ["oath","pea","eat","rain"] and board =

[
  ["o","a","a","n"],
  ["e","t","a","e"],
  ["i","h","k","r"],
  ["i","f","l","v"]
] 

Return ["eat","oath"].

字典樹 復雜度

時間 O(N^2logN) 空間 O(N)

思路

如果還像一中那樣,對每個詞進行一遍Word Search I,那復雜度就太高了。我們可以先用待查單詞建立一個字典樹,這樣我們在從矩陣中某個點開始深度優(yōu)先搜索時,可以直接用字典樹判斷當前組成的字符串是否是某個單詞的前綴。如果是某個單詞的前綴,再繼續(xù)搜索下去。字典樹同樣也提供search接口,所以同樣可以用于判斷是否已經(jīng)搜索到這個詞了。

注意

因為結果中不能有重復,我們可以在加入結果前先判斷是否已經(jīng)加過該結果,也可以稍微修改一下字典樹的search方法,使得每次我們搜索到一個單詞時,將其isEnd的標記置為false,這樣下次就不會搜索到這個詞了。

代碼
public class Solution {
    
    List res;
    Trie trie;
    
    public List findWords(char[][] board, String[] words) {
        res = new LinkedList();
        trie = new Trie();
        // 構建字典樹
        for(String word : words){
            trie.insert(word);
        }
        // 深度優(yōu)先搜索
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                helper(board, String.valueOf(board[i][j]), i, j);
            }
        }
        return res;
    }
    
    private void helper(char[][] board, String tmp, int i, int j){
        // 如果字典樹中存在該字符串,說明找到了單詞
        if(trie.search(tmp)){
            if(!res.contains(tmp)) res.add(tmp);
        }
        // 為了防止循環(huán),將當前字母改變一下
        board[i][j] ^= 255;
        // 對四個方向搜索,如果當前字符串是前綴就繼續(xù)搜索
        if(j < board[0].length - 1){
            String next = tmp + board[i][j+1];
            if(trie.startsWith(next)) helper(board, next, i, j + 1);
        }
        if(i > 0){
            String next = tmp + board[i-1][j];
            if(trie.startsWith(next)) helper(board, next, i - 1, j);
        }
        if(i < board.length - 1){
            String next = tmp + board[i+1][j];
            if(trie.startsWith(next)) helper(board, next, i + 1, j);
        }
        if(j > 0){
            String next = tmp + board[i][j-1];
            if(trie.startsWith(next)) helper(board, next, i, j - 1);
        }
        board[i][j] ^= 255;
    }
    
    // 字典樹的節(jié)點
    public class TrieNode {
        Character c;
        HashMap children;
        boolean isEnd;
        public TrieNode(char c){
            this.c = c;
            this.isEnd = false;
            this.children = new HashMap();
        }
    }
    
    // 字典樹
    public class Trie {
        TrieNode root;
        
        public Trie(){
            this.root = new TrieNode("r");
        }
        
        public void insert(String str){
            TrieNode curr = root, next = null;
            int idx = 0;
            for(int i = 0; i < str.length(); i++){
                next = curr.children.get(str.charAt(i));
                if(next == null){
                    next = new TrieNode(str.charAt(i));
                }
                if(i == str.length() - 1){
                    next.isEnd = true;
                }
                curr.children.put(str.charAt(i), next);
                curr = next;
            }
        }
        
        public boolean search(String str){
            TrieNode res = searchNode(str);
            return res != null && res.isEnd ? true : false;
        }
        
        public boolean startsWith(String str){
            TrieNode res = searchNode(str);
            return res == null ? false : true;
        }
        
        private TrieNode searchNode(String str){
            TrieNode curr = root, next = null;
            for(int i = 0; i < str.length(); i++){
                next = curr.children.get(str.charAt(i));
                if(next == null){
                    return null;
                }
                curr = next;
            }
            return next;
        }
    }
}

文章版權歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/64461.html

相關文章

  • [Leetcode] Word Search I&II 二維字符矩陣查找單詞

    摘要:復雜度時間空間為長度,為大小空間復雜度是是因為我用存信息,只動態(tài)地存當前的路徑如果用來存信息的話空間復雜度就是時間復雜度對每個點都要作為起始點,對于每個起始點,拓展一次有四個可能性四個鄰居,要拓展次長度為。思路暴力搜索帶走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...

    LuDongWei 評論0 收藏0
  • 前端 | 每天一個 LeetCode

    摘要:在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...

    張漢慶 評論0 收藏0
  • Leetcode】79.單詞搜索

    摘要:題目給定一個二維網(wǎng)格和一個單詞,找出該單詞是否存在于網(wǎng)格中。單詞必須按照字母順序,通過相鄰的單元格內(nèi)的字母構成,其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復使用。 題目 給定一個二維網(wǎng)格和一個單詞,找出該單詞是否存在于網(wǎng)格中。 單詞必須按照字母順序,通過相鄰的單元格內(nèi)的字母構成,其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允...

    Caicloud 評論0 收藏0
  • Leetcode】79.單詞搜索

    摘要:題目給定一個二維網(wǎng)格和一個單詞,找出該單詞是否存在于網(wǎng)格中。單詞必須按照字母順序,通過相鄰的單元格內(nèi)的字母構成,其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復使用。 題目 給定一個二維網(wǎng)格和一個單詞,找出該單詞是否存在于網(wǎng)格中。 單詞必須按照字母順序,通過相鄰的單元格內(nèi)的字母構成,其中相鄰單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允...

    ruicbAndroid 評論0 收藏0
  • [Leetcode] Word Break 單詞分解

    摘要:所以只要驗證滿足這個條件,我們則可以確定這個較長的字符串也是可分解的。同時,我們用數(shù)組記錄下字符串長度遞增時可分解的情況,以供之后使用,避免重復計算。當遍歷完這個詞典并找出所有以第一個字母開頭的詞以后,我們進入下一輪搜索。 Word Break I Given a string s and a dictionary of words dict, determine if s can ...

    Ververica 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<