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

LuDongWei 發(fā)布于2019-08-14 14:06 / 3447人閱讀

摘要：復(fù)雜度時(shí)間空間為長度，為大小空間復(fù)雜度是是因?yàn)槲矣么嫘畔ⅲ粍?dòng)態(tài)地存當(dāng)前的路徑如果用來存信息的話空間復(fù)雜度就是時(shí)間復(fù)雜度對每個(gè)點(diǎn)都要作為起始點(diǎn)，對于每個(gè)起始點(diǎn)，拓展一次有四個(gè)可能性四個(gè)鄰居，要拓展次長度為。思路暴力搜索帶走。

Word Search I

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.

DFS 復(fù)雜度

O(MN*4^K ) 時(shí)間 O(K) 空間
K為word長度， M*N為board大小
空間復(fù)雜度是K是因?yàn)槲矣肏ashSet存visited信息，只動(dòng)態(tài)地存當(dāng)前dfs的路徑；如果用boolean[][]來存visited信息的話空間復(fù)雜度就是O(MN)
時(shí)間復(fù)雜度：對每個(gè)點(diǎn)都要作為起始點(diǎn)dfs，對于每個(gè)起始點(diǎn)，拓展一次有四個(gè)可能性(四個(gè)鄰居)，要拓展k次(word長度為k)。

思路

暴力搜索帶走。

注意

visited可以有多種實(shí)現(xiàn)方法：

boolean[ ] [ ] visited

HashSet visited，用個(gè)小trick把二維坐標(biāo)轉(zhuǎn)化為一維

二維轉(zhuǎn)一維：(x,y) -> index : index = x * col + y

一維轉(zhuǎn)二維：index -> (x,y) : x = index / col; y = index % col;

直接修改board數(shù)組，將訪問過的格子改成特定字符比如 "#" 或者 "$"等

代碼

public class Solution {
    public boolean exist(char[][] board, String word) {
        HashSet visited = new HashSet();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (hasPath(0, i, j, word, board, visited))
                    return true;
            }
        }
        return false;
    }
    //找(x,y)是不是這個(gè)詞
    public boolean hasPath(int pos, int x, int y, String word, char[][] board, HashSet visited) {
        if (pos == word.length() - 1) {
            if (board[x][y] == word.charAt(pos))
                return true;
            else
                return false;
        }
        else {
            char target = word.charAt(pos);
            if (target == board[x][y]) {
                visited.add(x * board[0].length + y);
                int[] dirx = {0, 0, 1, -1};
                int[] diry = {1, -1, 0, 0};
                for (int i = 0; i < 4; i++) {
                    int newx = x + dirx[i];
                    int newy = y + diry[i];
                    if (isValid(newx, newy, board) && !visited.contains(newx * board[0].length + newy)) {
                            if (hasPath(pos + 1, newx, newy, word, board, visited))
                                return true;
                    }
                }
                visited.remove(x * board[0].length + y);
                return false;
            }
            else {
                return false;
            }
        }
    }
    public boolean isValid(int x, int y, char[][] board) {
        if (x >= 0 && x <= board.length - 1 && y >= 0 && y <= board[0].length - 1)
            return true;
        else
            return false;
    }
}

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"].

Trie + DFS 復(fù)雜度

O(MN*4^K ) 時(shí)間 O(MN) 空間
K為word最大長度， M*N為board大小
空間復(fù)雜度：用boolean[][]來存visited信息
時(shí)間復(fù)雜度：對每個(gè)點(diǎn)都要作為起始點(diǎn)dfs，對于每個(gè)起始點(diǎn)，拓展一次有四個(gè)可能性(四個(gè)鄰居)，要拓展k次(word最大長度為k)。

思路

要用trie，拿trie來dfs
先建trie，然后在board里搜所有trie里的word

遞歸函數(shù)接口:

public void hasPath(int x, int y, 
                    char[][] board, 
                    boolean[][] visited, 
                    Trie trie, 
                    StringBuilder sb, 
                    List result)

滿足的property：在進(jìn)入hasPath的一剎那，1.(x,y)還沒有訪問；2.(x,y)是valid的而且還沒有被訪問過；3.此時(shí)的dfs快照是sb和visited

注意

盡管visited可以有多種實(shí)現(xiàn)方法，這一題用1，3都可以，用2就會(huì)超時(shí)：

boolean[ ] [ ] visited

HashSet visited，用個(gè)小trick把二維坐標(biāo)轉(zhuǎn)化為一維

二維轉(zhuǎn)一維：(x,y) -> index : index = x * col + y

一維轉(zhuǎn)二維：index -> (x,y) : x = index / col; y = index % col;

直接修改board數(shù)組，將訪問過的格子改成特定字符比如 "#" 或者 "$"等

代碼

Trie Utility:

class Trie {
    private static final int R = 26;
    TrieNode root = new TrieNode();
    
    private static class TrieNode {
        private boolean isWord = false;
        private TrieNode[] children = new TrieNode[R];
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (cur.children[word.charAt(i) - "a"] == null) {
                cur.children[word.charAt(i) - "a"] = new TrieNode();
            }
            cur = cur.children[word.charAt(i) - "a"];
            if (i == word.length() - 1)
                cur.isWord = true;
        }
    }
    
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (cur.children[word.charAt(i) - "a"] == null)
                return false;
            else {
                if (i == word.length() - 1)
                    return cur.children[word.charAt(i) - "a"].isWord;
                else {
                    cur = cur.children[word.charAt(i) - "a"];
                }
            }
        }
        return false;
    }
    
    public boolean startsWith(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (cur.children[word.charAt(i) - "a"] == null) {
                return false;
            }    
            cur = cur.children[word.charAt(i) - "a"];
        }
        return true;
    }
    
}

主程序

public class Solution {
    public List findWords(char[][] board, String[] words) {
        List result = new ArrayList();
        Trie trie = new Trie();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (String str : words)
            trie.insert(str);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //帶著當(dāng)前的string去explore(i,j)這個(gè)點(diǎn)
                hasPath(i, j, board, visited, trie, new StringBuilder(), result);
            }
        }
        return result;
    }
    //x,y是合法的，sb里存得也是合法的，(x,y)還沒有explore
    public void hasPath(int x, int y, char[][] board, boolean[][] visited, Trie trie, StringBuilder sb, List result) {
        //explore (x,y)
        sb.append(board[x][y]);
        visited[x][y] = true;
        //does (x,y) make sense? do this only when it does
        if (trie.startsWith(sb.toString())) {
            if (trie.search(sb.toString())) {
                if (!result.contains(sb.toString()))
                    result.add(sb.toString());
            }
            int[] dirx = {0,0,1,-1};
            int[] diry = {1,-1,0,0};
            for (int i = 0; i < 4; i++) {
                int newx = x + dirx[i];
                int newy = y + diry[i];
                if (isValid(newx, newy, board) && !visited[newx][newy]) {
                    hasPath(newx, newy, board, visited, trie, sb, result);
                }
            }
        }
        //finished exploring (x,y),let"s go back explore another one
        visited[x][y] = false;
        sb.deleteCharAt(sb.length() - 1);
    }
    public boolean isValid(int x, int y, char[][] board) {
        if (x >= 0 && x <= board.length - 1 && y >= 0 && y <= board[0].length - 1)
            return true;
        else
            return false;
    }
}