Leetcode 212. Word Search II (tries树 + DFS)

题目：

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: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

一开始尝试了简单的DFS搜索，算法复杂度很高。

单独DFS版本代码：

class Solution {
public:
	vector<vector<char>> b;
	vector<string> ans;
	string s;
	int m;
	int n;
	void helper(string ss){
		s=ss;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(b[i][j]!=s[0]) continue;
				if(dfs(i,j,0)){
					ans.push_back(s);
					return;
				}
			}
		}
	}
	bool dfs(int x, int y,int d){    
		if(x<0 || x>=m ||y<0 || y>=n || s[d]!=b[x][y]) return false;
		if(d==s.size()-1) return true;
		char cur=b[x][y];
		b[x][y]='#';
		bool found=dfs(x+1,y,d+1) ||
				   dfs(x-1,y,d+1) ||
				   dfs(x,y+1,d+1) ||
				   dfs(x,y-1,d+1);
		b[x][y]=cur;
		return found;  
	}
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        b=board;
		m=board.size();
		n=board[0].size();
		for(int i=0;i<words.size();i++){
			helper(words[i]);
		}   
		return ans;  
    }
};

尝试加入 tries树，算法复杂度降低很多

tries树 + DFS：

class Solution {
public:
    struct TrieNode {
        TrieNode *child[26];
        string str;
        TrieNode() : str("") {
            for (auto &a : child) a = NULL;
        }
    };
    struct Trie {
        TrieNode *root;
        Trie() : root(new TrieNode()) {}
        void insert(string s) {
            TrieNode *p = root;
            for (auto &a : s) {
                int i = a - 'a';
                if (!p->child[i]) p->child[i] = new TrieNode();
                p = p->child[i];
            }
            p->str = s;
        }
    };
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        if (words.empty() || board.empty() || board[0].empty()) return res;
        vector<vector<bool>> visit(board.size(), vector<bool>(board[0].size(), false));
        Trie T;
        for (auto &a : words) T.insert(a);
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (T.root->child[board[i][j] - 'a']) {
                    search(board, T.root->child[board[i][j] - 'a'], i, j, visit, res);
                }
            }
        }
        return res;  
    }
    void search(vector<vector<char>>& board, TrieNode* p, int i, int j, vector<vector<bool>>& visit, vector<string>& res) { 
        if (!p->str.empty()) {
            res.push_back(p->str);
            p->str.clear();
        }
        int d[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        visit[i][j] = true;
        for (auto &a : d) {
            int nx = a[0] + i, ny = a[1] + j;
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && !visit[nx][ny] && p->child[board[nx][ny] - 'a']) {
                search(board, p->child[board[nx][ny] - 'a'], nx, ny, visit, res);
            }
        }
        visit[i][j] = false;
    }
};