My C++ solution based on trie (45ms)


  • 0
    W
    struct node{
        node* next[26];
        char c;
        bool isleaf;
        bool found;
        node():c('\0'), isleaf(false), found(false){
            for(int i=0; i<26; ++i) next[i]=NULL;
        }
        node(char ch):c(ch), isleaf(false), found(false){
            for(int i=0; i<26; ++i) next[i]=NULL;
        }
    };
    class Trie{
    public:
        Trie(){
            root = new node();
        }
        void insert(string word){
            node* p = root;
            for(int i=0; i<word.size(); ++i){
                int idx = word[i]-'a';
                if(!p->next[idx])
                    p->next[idx] = new node(word[i]);
                p = p->next[idx];
            }
            p->isleaf = true;
        }
        
        node* root;
    };
    class Solution {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            trie = new Trie();
            for(int i=0; i<words.size(); ++i) trie->insert(words[i]);
            vector<string> res;
            node* cur = trie->root;
            int m=board.size(), n=board[0].size();
            for(int i=0; i<m; ++i)
                for(int j=0; j<n; ++j){
                    string tmp = "";
                    helper(board, res, tmp, i, j, cur);
                }
            return res;
        }
    private:
        Trie* trie;
        void helper(vector<vector<char>>& board, vector<string>& res, string& tmp, int i, int j, node* cur){
            int m=board.size(), n=board[0].size();
            if(i<0||i==m||j<0||j==n||board[i][j]=='\0') return;
            int idx = board[i][j]-'a';
            node* next = cur->next[idx];
            if(!next) return;
            if(next&&next->isleaf&&!next->found){
                tmp.push_back(board[i][j]);
                res.push_back(tmp);
                next->found=true;
                tmp.pop_back();
            }
            char ch = board[i][j];
            board[i][j] = '\0';
            tmp.push_back(ch);
            helper(board, res, tmp, i-1, j, next);
            helper(board, res, tmp, i, j-1, next);
            helper(board, res, tmp, i+1, j, next);
            helper(board, res, tmp, i, j+1, next);
            tmp.pop_back();
            board[i][j] = ch;
        }
    };
    

Log in to reply
 

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