字符串搜索dfs题79_208_212

79. Word Search

给一个二维字符数组和一个字符串，判断是否存在一条路径使得路径字符等于所给字符串。

board =
[ [‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]]
Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.

从数组中每个字符处开始进行递归，看是否存在一个合法路径：

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++) {
            if (help(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
}

public boolean help(char[][] board, int i, int j, String word, int index) {
    if (word.length() == index)
        return true;

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
        return false;
    }

    char record = board[i][j];
    board[i][j] = '#';
    if (help(board, i-1, j, word, index+1) || help(board, i+1, j, word, index+1)
    || help(board, i, j-1, word, index+1) || help(board, i, j+1, word, index+1))
        return true;

    board[i][j] = record;
    return false;
}

208. Implement Trie (Prefix Tree)

实现一个Trie数据结构，具有insert, search, and startsWith方法，方法具体作用如例子所示。

Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // returns true
trie.search(“app”); // returns false
trie.startsWith(“app”); // returns true
trie.insert(“app”);
trie.search(“app”); // returns true

主要用嵌套数组实现，不懂为什么我代码逻辑和别人的一摸一样，但是速度却慢了一倍：

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

    public class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean is_word = false;
    }

    TrieNode root = new TrieNode();
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode nt = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (nt.children[index] == null) {
                nt.children[index] = new TrieNode();
            }
            nt = nt.children[index];
        }
        nt.is_word = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode nt = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (nt.children[index] == null)
                return false;

            nt = nt.children[index];
        }
        return nt.is_word;
    }

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

212. Word Search II

给一个二维字符数组和一个字符串列表，将所有在数组路径上的字符串返回。

79题的进阶版，79是存在问题，本题是查找，需要遍历所有路径，不过可以通过判断字符串前缀进行剪枝，所以要利用Trie数据结构，非常有效。

不过直接使用Trie的话速度无法达到极限，可以结合本题改造一下：

public List<String> findWords(char[][] board, String[] words) {
    TrieNode trie = new TrieNode();
    for (String s : words)
        trie.insert(s, trie);

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            help(board, i, j, new StringBuffer(""), trie);
        }
    }

    return res;
}

List<String> res = new ArrayList<>();
public void help(char[][] board, int i, int j, StringBuffer str, TrieNode trie) {
    char record = board[i][j];
    //如果该字符遍历过，或者不在任意一个字符串的前缀中时直接返回
    if (record == '#' || trie.children[record - 'a'] == null)
        return;

	//对二维数组递归的同时也对Trie递归，这样不用单独声明一个字符串来判断当前路径来
    trie = trie.children[record - 'a'];
    if (trie.word != null) {
        res.add(trie.word);
        trie.word = null;
    }

    board[i][j] = '#';
    if (i > 0) help(board, i-1, j, str, trie);
    if (i < board.length-1) help(board, i+1, j, str, trie);
    if (j > 0) help(board, i, j-1, str, trie);
    if (j < board[0].length) help(board, i, j+1, str, trie);
    board[i][j] = record;
}

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;

    public void insert(String word, TrieNode root) {
        TrieNode nt = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (nt.children[index] == null) {
                nt.children[index] = new TrieNode();
            }
            nt = nt.children[index];
        }
        //字符串储存完直接将其记录而不是判断是否是一个字符串
        nt.word = word;
    }
}