C++ simple solution


  • 0
    X
    struct TrieNode{
          vector<TrieNode*> a;
          bool isWord;
          TrieNode(){
              a = vector<TrieNode*>(26, NULL);
              isWord = false;
          }
    };
    class Trie{
            public:
                Trie(){
                    root = new TrieNode();
                }
                void insert(string str){
                    TrieNode* p = root;
                    for(int i = 0; i < str.length(); ++i){
                        if(p->a[str[i] - 'a'] == NULL){
                            p->a[str[i] - 'a'] = new TrieNode();
                        }
                        p = p->a[str[i] - 'a'];
                    }
                    p->isWord = true;
                }
                TrieNode* root;
    };
    class Solution {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            vector<string> ans;
            xsize = board.size();
            if(xsize == 0){
                return ans;
            }
            ysize = board[0].size();
            visit = vector<vector<bool>>(xsize, vector<bool>(ysize, false));
            for(int i = 0; i < words.size(); ++i){
                trie.insert(words[i]);
            }
            for(int i = 0;i < xsize; ++i){
                for(int j = 0;j < ysize; ++j){
                    string cur;
                    backtrack(i, j, cur, trie.root, ans, board);
                }
            }
            return ans;
        }
    private:
        Trie trie;
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        int xsize, ysize;
        vector<vector<bool>> visit;
        
        void backtrack(int i, int j, string& cur, TrieNode* root, vector<string>& ans, vector<vector<char>>& board){
            visit[i][j] = true;
            if(root->a[board[i][j] - 'a'] != NULL){
                root = root->a[board[i][j] - 'a'];
                cur.insert(cur.end(), board[i][j]);
                if(root->isWord){
                    ans.push_back(cur);
                    root->isWord = false;
                }
                for(int ii = 0; ii < 4; ++ii){
                    int x = i + dx[ii];
                    int y = j + dy[ii];
                    if(x >= 0 && x < xsize && y >= 0 && y < ysize && !visit[x][y]){
                        backtrack(x, y, cur, root, ans, board);
                    }
                }
                cur = cur.substr(0, cur.length() - 1);
            }
            visit[i][j] = false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.