Word Search Solutions in C++

// Source : https://oj.leetcode.com/problems/word-search/
// Author : Hao Chen
// Date   : 2014-07-19



#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool exist(vector<vector<char> > &board, string& word, int idx, int row, int col) {
    if ( row<0 || row>=board.size() ||
            col<0 || col>=board[0].size() ||
            board[row][col] != word[idx]) {
        return false;
    }


    if (idx+1 == word.size()) return true;

    //replace to a special char to avoid duplication.
    board[row][col] = '\0';

    if ( exist(board, word, idx+1, row+1, col ) ||
            exist(board, word, idx+1, row-1, col ) ||
            exist(board, word, idx+1, row, col+1 ) ||
            exist(board, word, idx+1, row, col-1 ) ) {
        return true;
    }

    //restore the char
    board[row][col] = word[idx];

    return false;
}

bool exist(vector<vector<char> > &board, string word) {
    if (board.size()<=0 || word.size()<=0) return false;
    int row = board.size();
    int col = board[0].size();

    for(int i=0; i<board.size(); i++) {
        for(int j=0; j<board[i].size(); j++){
            if ( board[i][j]==word[0]  ){
                if( exist(board, word, 0, i, j) ){
                    return true;
                }
            }
        }
    }
    return false;
}

vector< vector<char> > buildBoard(char b[][5], int r, int c) {
    vector< vector<char> > board;
    for (int i=0; i<r; i++){
        vector<char> v(b[i], b[i]+c);
        cout << b[i] << endl;
        board.push_back(v);
    }
    cout << "----------" << endl;    
    return board;
}

int main(int argc, char** argv)
{
    string s;
    char b[3][5] ={ "ABCE", "SFCS", "ADEE" };
    vector< vector<char> > board = buildBoard(b, 3, 4);

    s = "SEE";
    cout << s << ":" << exist(board, s) << endl; 

    s = "ABCCED";
    cout << s << ":" << exist(board, s) << endl; 

    s = "ABCB";
    cout << s << ":" << exist(board, s) << endl; 


    if (argc>1){
        s = argv[1];
        cout << s << ":" << exist(board, s) << endl; 
    }

    cout << endl << "----------" << endl;    
    char b1[3][5] ={ "CAA", "AAA", "BCD" };
    board = buildBoard(b1, 3, 3);

    s = "AAB";
    cout << s << ":" << exist(board, s) << endl; 


    cout << endl << "----------" << endl;    
    char b2[3][5] ={ "ABCE", "SFES", "ADEE" };
    board = buildBoard(b2, 3, 4);

    s = "ABCESEEEFS";
    cout << s << ":" << exist(board, s) << endl; 

    cout << endl << "----------" << endl;    
    char b3[3][5] ={ "aaaa", "aaaa", "aaaa" };
    board = buildBoard(b3, 3, 4);

    s = "aaaaaaaaaaaaa";
    cout << s << ":" << exist(board, s) << endl; 

    return 0;
}

/// Source : https://leetcode.com/problems/word-search/description/
/// Author : liuyubobobo
/// Time   : 2017-05-05

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Backtrack
// Time Complexity: O(m*n*m*n)
// Space Complexity: O(m*n)
class Solution {

private:
    int d[4][2] = {{-1, 0}, {0,1}, {1, 0}, {0, -1}};
    int m, n;
    vector<vector<bool>> visited;

    bool inArea( int x , int y ){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    // start from board[startx][starty], find word[index...word.size())
    bool searchWord( const vector<vector<char>> &board, const string& word, int index,
                    int startx, int starty ){

        //assert( inArea(startx,starty) );
        if( index == word.size() - 1 )
            return board[startx][starty] == word[index];

        if( board[startx][starty] == word[index] ){
            visited[startx][starty] = true;
            for( int i = 0 ; i < 4 ; i ++ ){
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if( inArea(newx, newy) && !visited[newx][newy] &&
                    searchWord(board, word, index + 1, newx, newy))
                    return true;
            }
            visited[startx][starty] = false;
        }
        return false;
    }

public:
    bool exist(vector<vector<char>>& board, string word) {

        m = board.size();
        assert( m > 0 );
        n = board[0].size();
        visited = vector<vector<bool>>(m, vector<bool>(n, false));
        for( int i = 0 ; i < board.size() ; i ++ )
            for( int j = 0 ; j < board[i].size() ; j ++ )
                if( searchWord( board, word, 0 , i, j) )
                    return true;

        return false;
    }
};

int main() {

    char b1[3][4] = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    vector<vector<char>> board1;
    for( int i = 0 ; i < 3 ; i ++ )
        board1.push_back(vector<char>(b1[i], b1[i] + sizeof(b1[i]) / sizeof(char)));

    int cases = 3;
    string words[3] = {"ABCCED" , "SEE" , "ABCB" };
    for( int i = 0 ; i < cases ; i ++ )
        if(Solution().exist(board1,words[i]))
            cout<<"found "<<words[i]<<endl;
        else
            cout<<"can not found "<<words[i]<<endl;

    // ---

    char b2[1][1] = {{'A'}};
    vector<vector<char>> board2;
    for(int i = 0 ; i < 3 ; i ++)
        board2.push_back(vector<char>(b2[i],b2[i]+sizeof(b2[i])/sizeof(char)));

    if(Solution().exist(board2,"AB"))
        cout<<"found AB"<<endl;
    else
        cout<<"can not found AB"<<endl;

    return 0;
}