Word Search II

Word Search II

Given a 2D board and a list of words from the dictionary, find all words on the board.

Each word must be constructed from letters of a sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

 

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

 

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

 class Solution {

    struct node{

        char c;

        int end;

        string word;

        node *child[26];

    };

    struct node *getNew(char ch)

    {

         node *t=new node;

        t->c=ch;

        t->end=0;

        t->word="";

        for(int i=0;i<26;++i)

            t->child[i]=NULL;

        return t;

    }

     node *root=getNew('/');

    void insert(string s)

    {

        node *curr=root;

        for(auto w:s)

        {

            if(curr->child[w-'a']==nullptr)

                curr->child[w-'a']=getNew(w);

              curr=curr->child[w-'a'];

        }

        curr->end+=1;

        curr->word=s;

        

    }

    

     void solve(vector<vector<char> > &board,int i,int j,int n,int m,vector<string> &ans,node *curr)

    {

         int l=board[i][j]-'a';

        if(board[i][j]=='$'||curr->child[l]==NULL)return ;

          curr=curr->child[l];

        if(curr->end>0)

        {

            ans.push_back(curr->word);

            curr->end-=1;

        }

          char ch=board[i][j];

         board[i][j]='$';

        if(i>0)

            solve(board,i-1,j,n,m,ans,curr);

        if(j>0)

            solve(board,i,j-1,n,m,ans,curr);

        if(i<n-1)

            solve(board,i+1,j,n,m,ans,curr);

        if(j<m-1)

            solve(board,i,j+1,n,m,ans,curr);

        

         board[i][j]=ch;     

    }

public:

   

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) 

{

        int n=board.size(),m=board[0].size();

           for(auto w:words)

               insert(w);

        

        vector<string> ans;

        for(int i=0;i<n;++i)

        {

            for(int j=0;j<m;++j)

            {

                solve(board,i,j,n,m,ans,root);

            }

        }

        return ans;

        

}

};