Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

C++:
01 bool wordExist(vector<vector<char> >& board,
02      set<pair<int, int> > visited, string word, pair<int, int> cur)
03 {
04     if(word.size()==0)
05         return true;
06     char c=word[0];
07     int x=cur.first;
08     int y=cur.second;
09     if((x1>=0)&&(board[x1][y]==c)&&
10        visited.find(pair<int,int>(x1,y))== visited.end())){
11        visited.insert(pair<int,int>(x1,y));
12        if(wordExist(board,visited,
13                     word.substr(1),pair<int, int>(x1,y)))
14            return true;
15        else
16           visited.erase(pair<int,int>(x1,y));
17     }
18     if((x+1<board.size())&&(board[x+1][y]==c)&&
19        visited.find(pair<int, int>(x+1,y))==visited.end())){
20        visited.insert(pair<int,int>(x+1,y));
21        if(wordExist(board,visited,
22                     word.substr(1),pair<int,int>(x+1,y)))
23            return true;
24        else
25           visited.erase(pair<int,int>(x+1,y));
26     }
27     if((y1>=0)&&(board[x][y1]==c)&&
28        (visited.find(pair<int,int>(x,y1))==visited.end())){
29        visited.insert(pair<int,int>(x,y1));
30        if(wordExist(board,visited,
31                     word.substr(1),pair<int,int>(x,y1)))
32            return true;
33        else
34            visited.erase(pair<int,int>(x,y1));
35     }
36     if((y+1<board[x].size())&&(board[x][y+1]==c)&&
37        (visited.find(pair<int,int>(x,y+1))==visited.end())){
38        visited.insert(pair<int,int>(x,y+1));
39        if(wordExist(board,visited,
40                     word.substr(1),pair<int,int>(x,y+1)))
41            return true;
42        else
43            visited.erase(pair<int,int>(x,y+1));
44     }
45     return false;
46 }
47 
48 bool exist(vector<vector<char> > &board, string word) {
49      for(int i=0;i<board.size();i++){
50          for(int j=0;j<board[i].size();j++){
51              if(board[i][j]==word[0]){
52                  set<pair<int,int> >visited;
53                  visited.insert(pair<int,int>(i,j));
54                  if(wordExist(board, visited,
55                     word.substr(1), pair<int,int>(i,j))==true)
56                      return true;
57              }
58          }
59      }
60      return false;
61 }
Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Word Search

  1. aastha says:

    Hey! Excellent Code!! I tried to change recursion to loops, but then it failed on certain cases.. like searching for “SEE” … could u help me track d mistake?

    bool exist(vector<vector > &board, string word) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    for(int i=0;i<board.size();i++){
    for(int j=0;j<board[i].size();j++){
    if(board[i][j]==word[0]){
    set<pair >visited;
    visited.insert(pair(i,j));
    if(wordExist(board, visited,
    word.substr(1), pair(i,j))==true)
    return true;
    }
    }
    }
    return false;
    }

    bool wordExist(vector<vector >& board,
    set<pair > visited, string word, pair cur)
    {
    if(word.size()==0)
    return true;
    char c=word[0];
    int x=cur.first;
    int y=cur.second;
    string cword=word;
    while((word.size())&&(x!=-1)&&(y!=-1)){
    char c=word[0];
    if((x-1>=0)&&(board[x-1][y]==c)&&(visited.find(pair(x-1,y))== visited.end())){
    visited.insert(pair(x-1,y));
    x=x-1;
    word=word.substr(1);
    }
    else if((x+1<board.size())&&(board[x+1][y]==c)&&(visited.find(pair(x+1,y))==visited.end())){
    visited.insert(pair(x+1,y));
    x=x+1;
    word=word.substr(1);
    }
    else if((y-1>=0)&&(board[x][y-1]==c)&&(visited.find(pair(x,y-1))==visited.end())){
    visited.insert(pair(x,y-1));
    y=y-1;
    word=word.substr(1);
    }
    else if((y+1<board[x].size())&&(board[x][y+1]==c)&&(visited.find(pair(x,y+1))==visited.end())){
    visited.insert(pair(x,y+1));
    y=y+1;
    word=word.substr(1);
    }
    else{
    visited.erase(pair(x,y));
    return false;
    }

    }

    if(word.size()==0)
    return true;
    else
    return false;
    }

    • askmecode says:

      Thank you for your question. It is a worth try to make this iterative instead of recursive. However, I think it may be much more difficult, since this problem does not have a clean obvious sub-problem structure.
      I look at your code and I think there is a problem , since every time you only track one path instead of 4. That is why you may miss some potential solutions. When you check the current character, there might be multiple ways to go. But, since you use if else structure, you will just pick the first match direction and follow that direction. Unfortunately, that direction may fail while other direction may be the right direction to go.

      • aastha says:

        hey! thanks for the reply .. yes i got the issue … n cant think of a decent workaround .. it is not wise to check till all are visited … thanks fr d help deir!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s