单词搜索

212. 单词搜索 II

思路:

虽然明明知道硬写一定会,超时,但还是写了一个。

超时后考虑什么优化:自然想到了字典树。不过没有想透彻:

  • 用字典树构造dfs遍历的路径,❌ :dfs搜索的路径不需要被查询,因为只出现一次

  • 正确做法:用字典树存储所有words,方便查询。或者进一步的,在dfs过程中,可以直接用字典树进行搜索剪枝。

    Orz

代码

一般的搜索剪枝:

class Solution {
    int n, m;
    int vis[20][20];

    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> findStrs;
        n = board.size();
        if(n == 0) return {};
        m = board[0].size();

        for(auto s : words) {
            if(isInBoard(s, board)) {
                findStrs.push_back(s);
            }
        }
        return findStrs;
    }

    bool isInBoard(string &target, vector<vector<char>>& board) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == target[0]) {
                    if(_dfs(board, target, i, j, 0)) return true;
                }
            }
        }
        return false;
    }

    bool _dfs(vector<vector<char>>& board, string &target, int x, int y, int pos) {
        if(pos + 1 == target.size()) {
            return true;
        }
        
        vis[x][y] = 1;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] == 1) continue;
            if(board[nx][ny] == target[pos + 1]) {
                if(_dfs(board, target, nx, ny, pos + 1)) {
                    vis[x][y] = 0;
                    return true;
                }
            }
        }
        vis[x][y] = 0;
        return false;
    }

};

字典树优化的搜索剪枝:

class TierNode { 
public:
    TierNode* child[26];
    bool isWord;
    string word;

    TierNode() {
        memset(child, 0, sizeof(child));
        isWord = false;
    }
};

class Tier { 
    TierNode* root;
public:
    Tier() {
        root = new TierNode();
    }


    void insert(string word) {
        auto cur = root;
        for(auto c : word) {
            if(cur->child[c - 'a'] == NULL) {
                cur->child[c - 'a'] = new TierNode();
            }
            cur = cur->child[c - 'a'];
        }
        cur->isWord = true;
        cur->word = word;
    }

    bool contain(string word) {
        auto cur = root;
        for(auto c : word) {
            if(cur->child[c - 'a'] == NULL) {
                return false;
            }
            cur = cur->child[c - 'a'];
        }
        if(cur->isWord) return true;
        return false;
    }

    TierNode* getRoot() {
        return root;
    }
};


class Solution {
    int n, m;
    int vis[20][20];

    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0}; 

    vector<string> findStrs; 
    set<string> sset;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        n =  board.size();
        if(n == 0) return {};
        m = board[0].size();

        Tier tree;
        for(auto s : words) {
            tree.insert(s);
        }
   
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                auto node = tree.getRoot()->child[board[i][j] - 'a'];
                if(node) {
                    dfs(board, node, i, j);
                }

            }
        }
        
        for(auto s: sset) {
            findStrs.push_back(s);
        }
        return findStrs;
    }

    void dfs(vector<vector<char>>& board, TierNode *node, int x, int y) {
        if(node->isWord) sset.insert(node->word);
        
        vis[x][y] = 1;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] == 1) continue;
            auto next = node->child[board[nx][ny] - 'a'];
            if(next != NULL) {
                dfs(board, next, nx, ny);
            }
        }
        vis[x][y] = 0;
        return;
    }

};

Comments