getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more

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.

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 10^4
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

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

class Solution {
private:
    bool safe(int i, int j, vector<vector<bool>> &vis) {
        return (i >= 0 && i < vis.size() && j >= 0 && j < vis[0].size() && !vis[i][j]);
    }
    void solve(vector<string> &ans, vector<vector<char>>& board, vector<vector<bool>> &vis, string &s,
    int row, int col, int idx, int &flag){
        if (!safe(row, col, vis) || board[row][col] != s[idx])
            return;
        if(idx+1==s.size()){
            flag=1;
            ans.push_back(s);
            return;
        }

        vis[row][col] = true;
        solve(ans, board,vis, s, row + 1, col, idx + 1,flag); 
        vis[row][col] = false; 
        if(flag==1) return;

        vis[row][col] = true; 
        solve(ans, board,vis, s, row - 1, col, idx + 1,flag); 
        vis[row][col] = false;
        if(flag==1) return;

        vis[row][col] = true; 
        solve(ans, board,vis, s, row, col + 1, idx + 1,flag); 
        vis[row][col] = false;
        if(flag==1) return;

        vis[row][col] = true; 
        solve(ans, board,vis, s, row, col - 1, idx + 1,flag); 
        vis[row][col] = false;
        if(flag==1) return;

        return;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ans;
        vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),0));
        for(int i=0;i<words.size();i++){
            int flag=0;
            for(int j=0;j<board.size();j++){
                for(int k=0;k<board[0].size();k++){
                    solve(ans,board,vis,words[i],j,k,0,flag);
                    if(flag==1) break;
                }
                if(flag==1) break;
            }
        }
        return ans;
    }
};

I am doing this question using backtracking as specified by the tag of the question. Although my code is giving correct answer , it is giving TLE for very large input. I have tried optimizing the code as much as i could. So i need your help further optimizing the same approach.

You can insert all the given words into a trie, and only continue searching along a path while the current string is a prefix of some word in the trie.

Sample implementation (based on your code, with some modifications):

struct TrieNode {
    TrieNode* children[26]{};
    bool wordEnd, found;
    ~TrieNode() {
        for (auto n : children) delete n;
    }
} *root;
void insert(const string& s) {
    auto curr = root;
    for (char c : s) {
        c -= 'a';
        if (!curr->children[c]) curr->children[c] = new TrieNode();
        curr = curr->children[c];
    }
    curr->wordEnd = true;
}
class Solution {
private:
    bool safe(int i, int j, vector<vector<bool>> &vis) {
        return i >= 0 && i < vis.size() && j >= 0 && j < vis[0].size() && !vis[i][j];
    }
    void solve(vector<string> &ans, vector<vector<char>>& board, vector<vector<bool>> &vis, string& s, TrieNode* node, int row, int col){
        if (!safe(row, col, vis) || !(node = node->children[board[row][col] - 'a'])) return;
        s += board[row][col];
        if (node->wordEnd && !node->found) node->found = true, ans.push_back(s);
        vis[row][col] = true;
        solve(ans, board, vis, s, node, row + 1, col); 
        solve(ans, board, vis, s, node, row - 1, col); 
        solve(ans, board, vis, s, node, row, col + 1); 
        solve(ans, board, vis, s, node, row, col - 1); 
        vis[row][col] = false;
        s.pop_back();
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        root = new TrieNode();
        for (const auto& word : words) insert(word);
        vector<vector<bool>> vis(board.size(),vector<bool>(board[0].size(),0));
        string curr;
        vector<string> ans;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                solve(ans, board, vis, curr, root, i, j);
            }
        }
        delete root;
        return ans;
    }
};

Note that there is a faster trie implementation that does not perform dynamic memory allocation (using the problem constraints instead), but it is not necessary for this problem and tends to be harder to read.