leetcode-word-search-ii

题目大意

　　https://leetcode.com/problems/word-search-ii/

　　接续https://leetcode.com/problems/word-search/，给你的不是一个word，而是一个word数组，让你找出所有符合条件的word

题目分析

　　暴力解法是直接借助word search的程序对于输入的word数组的每个单词都进行搜索，这样复杂度很高，比如”abcdef”和“abcdeg”，两个单词前边跟多位都是一样，如果调用两次DFS，显然会有大量的重复路径搜索。因此很容易想到trie树，先将word的list构建成一颗trie树，对trie树进行DFS，同时查看trie树上的路径是否在board中，具体可以看下代码。

代码

class TrieNode {
    
    public TrieNode[] childNodes;
    public int freq; //词频
    public char nodeChar;
    // Initialize your data structure here.
    public TrieNode() {
        childNodes = new TrieNode[26];
        freq = 0;
    }
}

class Trie {
    public TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        if(word.length() == 0) {
            return;
        }
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            int k = word.charAt(i) - 'a';
            if(cur.childNodes[k] == null) {
            	cur.childNodes[k] = new TrieNode();
            	cur.childNodes[k].nodeChar = word.charAt(i);
            }
            cur = cur.childNodes[k];
            if(i == word.length() - 1) {
            	cur.freq ++;
            }
        }
    }

    // Returns if the word is in the trie.
    //root->'a'->'b'->'c'
    public boolean search(String word) {
        if(word.length() == 0) {
        	return false;
        }
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            int k = word.charAt(i) - 'a';
            if(cur.childNodes[k] == null) {
                return false;
            }
            cur = cur.childNodes[k];
        }
        if(cur.freq > 0) {
        	return true;
        } else {
        	return false;
        }
    }

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

public class Solution {
    
    private int row;
    private int col;
    private List<String> ans;
    private char[][] b;
    private char[] path;
    
    private boolean check(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
    
    private void dfs(TrieNode root, int x, int y, int idx) {
        
        if (!check(x, y)) {
            return;
        }
        TrieNode[] childs = root.childNodes;
        if (childs == null || childs.length == 0) {
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (childs[i] == null) {
                continue;
            }
            char ch = childs[i].nodeChar;
            if (ch == b[x][y]) {
                path[idx] = ch;
                
                if (childs[i].freq > 0) {
                    StringBuilder sb = new StringBuilder();
                    for (int ii = 0; ii <= idx; ii++) {
                        sb.append(path[ii]);
                    }
                    ans.add(sb.toString());
                    childs[i].freq = 0; // 一定要置为0，否则会重复添加
                }
                // 四个方向搜索
                b[x][y] = '.';
                dfs(childs[i], x + 1, y, idx + 1);
                
                b[x][y] = '.';
                dfs(childs[i], x - 1, y, idx + 1);
                
                b[x][y] = '.';
                dfs(childs[i], x, y + 1, idx + 1);
                    
                b[x][y] = '.';
                dfs(childs[i], x, y - 1, idx + 1);
                
                b[x][y] = ch; //回溯
                break;
            }
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return new ArrayList<String>();
        }
        row = board.length;
        col = board[0].length;
        ans = new ArrayList<String>();
        b = board;
        path = new char[row * col];
        // build trie tree
        Trie trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dfs (trie.root, i, j, 0);
            }
        }
        return ans;
    }
}

　　时间复杂度待分析。