<p>Given an <code>m x n</code> grid of characters <code>board</code> and a string <code>word</code>, return <code>true</code> <em>if</em> <code>word</code> <em>exists in the grid</em>.</p>

<p>The word can 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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word2.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCCED&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;SEE&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/15/word3.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCB&quot;
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n = board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 6</code></li>
	<li><code>1 &lt;= word.length &lt;= 15</code></li>
	<li><code>board</code> and <code>word</code> consists of only lowercase and uppercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you use search pruning to make your solution faster with a larger <code>board</code>?</p>

void search(vector<vector<char>>board,string word,int i,int j,int pos,string result,vector<vector<int>> check,vector<bool> & output){
    if(result == word){
        output.push_back(true);
        return;
    }
    string temp = result;
    int repeat = 0;
    if((i-1) != -1){
        if(board[i-1][j] == word[pos+1]){
            for(int x = 0;x < check.size();x++){
                if(check[x][0] == i-1 and check[x][1] == j){
                    repeat = 1;
                }
            }
            if(repeat != 1){
                string h(1,word[pos+1]);
                temp.append(h);
                vector<int> check1 = {i-1,j};
                check.push_back(check1);
                search(board,word,i-1,j,pos+1,temp,check,output);
                check.pop_back();
            }
        }
    }
    temp = result;
    repeat = 0;
    if((i+1) != board.size()){
        if(board[i+1][j] == word[pos+1]){
            for(int x = 0;x < check.size();x++){
                if(check[x][0] == i+1 and check[x][1] == j){
                    repeat = 1;
                }
            }
            if(repeat != 1){
                string h(1,word[pos+1]);
                temp.append(h);
                vector<int> check1 = {i+1,j};
                check.push_back(check1);
                search(board,word,i+1,j,pos+1,temp,check,output);
                check.pop_back();
            }
        }
    }
    temp = result;
    repeat = 0;
    if((j-1) != -1){
        if(board[i][j-1] == word[pos+1]){
            for(int x = 0;x < check.size();x++){
                if(check[x][0] == i and check[x][1] == j-1){
                    repeat = 1;
                }
            }
            if(repeat != 1){
                string h(1,word[pos+1]);
                temp.append(h);
                vector<int> check1 = {i,j-1};
                check.push_back(check1);
                search(board,word,i,j-1,pos+1,temp,check,output);
                check.pop_back();
            }
        }
    }
    temp = result;
    repeat = 0;
    if((j+1) != board[0].size()){
        if(board[i][j+1] == word[pos+1]){
            for(int x = 0;x < check.size();x++){
                if(check[x][0] == i and check[x][1] == j+1){
                    repeat = 1;
                }
            }
            if(repeat != 1){
                string h(1,word[pos+1]);
                temp.append(h);
                vector<int> check1 = {i,j+1};
                check.push_back(check1);
                search(board,word,i,j+1,pos+1,temp,check,output);
                check.pop_back();
            }
        }
    }
    temp = result;
    repeat = 0;
    return;
}

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        // word length > size of board
        if((board.size() * board[0].size()) < word.size()){
            return false;
        }
        // letter in word doesn't exist on board
        int a = 0;
        while(a != word.size()){
            int done = 0;
            for(int i = 0;i < board.size();i++){
                for(int j = 0;j < board[0].size();j++){
                    if(word[a] == board[i][j]){
                        done = 1;
                        break;
                    }
                }
                if(done == 1){
                    a++;
                    break;
                }
            }
            if(done == 1){
                continue;
            }
            return false;
        }
        //start search from backwards instead from front in word
        int count1 = 0;
        int count2 = 0;
        for(int i = 0;i < board.size();i++){
            for(int j = 0;j < board[0].size();j++){
                if(board[i][j] == word[0]){
                    count1+=1;
                }
                else if(board[i][j] == word[word.size()-1]){
                    count2+=1;
                }
            }
        }
        if (count1 > count2){
            string word1  = word;
            for(int i = word.size()-1;i >= 0;i--){
                word[word.size()-1-i] = word1[i];
            }
        }
        for(int i = 0;i < board.size();i++){
            for(int j = 0;j < board[0].size();j++){
                if(board[i][j] == word[0]){
                    string h(1,word[0]);
                    string result = h;
                    int pos = 0;
                    vector<bool> output;
                    vector<vector<int>> check = {{i,j}};
                    search(board,word,i,j,pos,result,check,output);
                    for(int i = 0;i < output.size();i++){
                        if(output[i] == true){
                            return true;
                        }
                    }
                }
            }
        }
    return false;
    }
};
30368