LeetCode Q79: 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 =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

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


Solution:
My solution is very conventional that I use two array to track which entries are already on the path and how many neighbors (up, down, left, right) are already accessed.

	bool exist(vector<vector<char> >& board, string word) {
	stack<int> myStack;
	if(board.empty())
	return false;
	int rows=board.size();
	int cols=board[0].size();
	int p=-1;
	vector<int> flag(rows*cols, 0);
	vector<int> nbflag(rows*cols, 0);
	int count=0;
	while(p<rows*cols){
	if(myStack.empty()){
	p++;
	if(p==rows*cols)
	return count==word.length();
	if(board[p/cols][p%cols]!=word[0])
	continue;
	flag.clear();
	myStack.push(p);
	flag[p]=1;
	count++;
	}else{
	int topp=myStack.top();
	int up=(topp-cols)<0? topp:topp-cols;
	int down=(topp+cols)>=rows*cols? topp:topp+cols;
	int left=(topp%cols)==0? topp: topp-1;
	int right=(topp%cols)==cols-1? topp: topp+1;
	if(board[up/cols][up%cols]==word[count]&&flag[up]==0&&nbflag[topp]<1){
	myStack.push(up);
	flag[up]=1;
	count++;
	nbflag[topp]=1;
	continue;
	}
	if(board[down/cols][down%cols]==word[count]&&flag[down]==0&&nbflag[topp]<2){
	myStack.push(down);
	flag[down]=1;
	count++;
	nbflag[topp]=2;
	continue;
	}
	if(board[left/cols][left%cols]==word[count]&&flag[left]==0&&nbflag[topp]<3){
	myStack.push(left);
	flag[left]=1;
	count++;
	nbflag[topp]=3;
	continue;
	}
	if(board[right/cols][right%cols]==word[count]&&flag[right]==0&&nbflag[topp]<4){
	myStack.push(right);
	flag[right]=1;
	count++;
	nbflag[topp]=4;
	continue;
	}
	if(count==word.length())
	return true;
	flag[topp]=0;
	nbflag[topp]=0;
	myStack.pop();
	count--;
	}
	}
	return count==word.length();
	}

view raw Q79WordSearch.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	bool helper(vector<vector<char> >& board, vector<vector<int> >& used, string word, int idx, int row, int col){
	int dir[8]={0, -1, 0, 1, -1, 0, 1, 0};
	if(idx == word.length()-1&&word[idx]==board[row][col])
	return true;
	bool res=false;
	if(word[idx]!=board[row][col])
	return false;
	for(int i=0; i<4; i++){
	int rr = row+dir[i*2];
	int cc = col+dir[i*2+1];
	if(rr<0||rr>board.size()-1||cc<0||cc>board[0].size()-1||used[rr][cc]==1)
	continue;
	used[rr][cc]=1;
	res = res + helper(board, used, word, idx+1, rr, cc);
	used[rr][cc]=0;
	if(res)
	break;
	}
	return res;
	}
	bool exist(vector<vector<char> >& board, string word) {
	if(board.empty())
	return false;
	vector<vector<int> > used(board.size(), vector<int>(board[0].size(), 0));
	for(int i=0; i<board.size(); i++){
	for(int j=0; j<board[0].size(); j++){
	used[i][j]=1;
	bool res = helper(board, used, word, 0, i, j);
	used[i][j]=0;
	if(res)
	return true;
	}
	}
	return false;
	}
	};

view raw Q79-2.cpp hosted with ❤ by GitHub