c++ - My word search II solution is very slow (Leetcode 212)

Question

My solution is correct and passes all test cases, but my solution is very slow (faster than 7% of C++ solutions).

Question: Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For 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"]

By the way, I don't have Leetcode premium and looked at the discussion. I see that other people are using recursion. I am using a stack, but this shouldn't really be a problem. Does anyone see any performance issues with my code? The complexity should be O(n^2*3^n)

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ret;
        Trie* root = new Trie();
        for (const auto &i:words) {
            root->insert(i);
        }
        Trie* cnode = root;
        int numRow = board.size();
        int numCol = board[0].size();
        
        vector<int> temp(numCol, 0);
        vector<vector<int>> visited(numRow, temp);

        for (int i = 0; i < numRow; ++i) {
            for (int j = 0; j < numCol; ++j) {
                
                stack<pair<int, int>> searcher;
                searcher.push(make_pair(i,j));
                
                while (!searcher.empty()) {
                    int row = searcher.top().first;
                    int col = searcher.top().second;
                    int cur = board[row][col] - 97;
                    
                    if (visited[row][col]) {
                        cnode = cnode->parent;
                        visited[row][col] = 0;
                        searcher.pop();
                    } else if (cnode->child[cur] == nullptr) {
                        searcher.pop();
                        visited[row][col] = 0;
                    } else {
                        visited[row][col] = 1;

                        cnode = cnode->child[cur];

                        if (cnode->contain != "") {
                            ret.push_back(cnode->contain);
                            cnode->contain = "";
                        }
                        if (row + 1 < numRow && !visited[row + 1][col]) {
                            searcher.push(make_pair(row+1, col));
                        }
                        if (row - 1 >= 0 && !visited[row-1][col]) {
                            searcher.push(make_pair(row-1, col));
                        }
                        if (col + 1 < numCol && !visited[row][col+1]) {
                            searcher.push(make_pair(row, col+1));
                        }
                        if (col - 1 >= 0 && !visited[row][col-1]) {
                            searcher.push(make_pair(row, col-1));
                        }
                        
                    }
                }
            }
        }
        
        return ret;
    }
    
    class Trie {
        public:
        vector<Trie*> child;
        Trie* parent;
        string contain;
        Trie() {
            child = vector<Trie*>(26, nullptr);
            contain = "";
            parent = nullptr;
        }
        void insert(string word) {
            Trie* root = this;
            for (int i = 0; i < word.size(); ++i) {
                int loc = word[i] - 97;
                
                if (root->child[loc] == nullptr) {
                    root->child[loc] = new Trie();
                    root->child[loc]->parent = root;
                }
                root = root->child[loc];
            }
            root->contain = word;
            
        }
    };
}; 

Answer 1

等待大神答复