C++ Simple Solution, Trie, Backtrace, DFS


  • 0
    class Solution {
    private:
        class Node {
        public:
            char c;
            string word;
            Node* next[26];
            Node(char c = '.') : c(c) {
                fill_n(next, 26, nullptr);
            }
            ~Node() {
                for (auto& i : next)
                    delete i;
            }
        };
        
        void dfs(Node* cur, vector<vector<char>>& board, vector<string>& res, int r, int c) {
            char def = board[r][c];
            board[r][c] = '\0';
            int m = board.size(), n = board[0].size();
            if (cur->word.size() && mp.find(cur->word) == mp.end()) {
                res.push_back(cur->word);
                mp[cur->word] = true;
            }
            vector<pair<int, int>> nei = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (auto i : nei) {
                int rr = r + i.first, cc = c + i.second;
                if (rr < 0 || rr >= m || cc < 0 || cc >= n || board[rr][cc] == '\0' ||
                    cur->next[board[rr][cc] - 'a'] == nullptr)
                    continue;
                dfs(cur->next[board[rr][cc] - 'a'], board, res, rr, cc);
            }
            board[r][c] = def;
        }
        
        unordered_map<string, bool> mp;
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            int m = board.size(), n = m ? board[0].size() : 0;
            vector<string> res;
            Node* root = new Node();
            for (auto& word : words) {
                Node* cur = root;
                for (auto c : word) {
                    if (cur->next[c - 'a'] == nullptr) {
                        cur->next[c - 'a'] = new Node(c);
                    }
                    cur = cur->next[c - 'a'];
                }
                cur->word = word;
            }
            
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (root->next[board[i][j] - 'a'])
                        dfs(root->next[board[i][j] - 'a'], board, res, i, j);
            delete root;
            return res;
        }
    };
    

Log in to reply
 

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