Search a word in a given 2 dimensional matrix of letters



Backtracking : Program to search a word in a given 2 dimensional matrix of letters

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>

using namespace std;

class WordSearch {

    public:
    string sofar;
    vector<string> board;
    string word;

    // The size of the board would always be less than or equal to 8
    bool visited[8][8] = {{ false }};

    bool Search (int x, int y, int pos) {

        if (pos == word.size()) {
            return true;
        } else {
            // Co-ordinates difference of the adjacent cells in order Up, Right, Down and Left
            int dx[4] = { -1, 0, 1, 0 };
            int dy[4] = { 0, 1, 0, -1 };
            int rows = board.size();
            int cols = board[0].size();

            // Visit adjacent cells in order Up, Right, Down & Left
            for (int i=0; i<4; i++) {

                int newx = x + dx[i];
                int newy = y + dy[i];

                if (newx < 0 or newx >= rows or
                    newy < 0 or newy >= cols or visited[newx][newy] == true)
                    continue;

                if (board[newx][newy] == word[pos]) {
                    pos++;
                    visited[newx][newy] = true;
                    if (Search (newx, newy, pos) == true) // Word has been found so return true.
                        return true;
                    visited[newx][newy] = false; // Backtrack and try other adjacent letter first.
                    pos--;
                }
            }
        }
        return false;
    }

    // Below function returns true if the word [word] exist on the board
    bool Exist (vector<string> arg_board, string arg_word) {

        int pos; // Tracks the position of the matching letters of the word
        board = arg_board;
        word = arg_word;

        int rows = board.size();
        int cols = board[0].size();

        memset(visited, false, sizeof(bool) * 8 * 8);

        for (int r=0; r<rows; r++) {
            for (int c=0; c<cols; c++) {
                pos = 0;
                if (board[r][c] == word[pos]) {
                    pos++;
                    visited[r][c] = true;
                    if (Search(r, c, pos))
                        return true;
                    visited[r][c] = false;
                }
            }
        }
        return false;
    }
};

int main() {

    WordSearch W;
    //====================================
    vector<string> vec_1 = {{"ABCE"},
                            {"SFCS"},
                            {"ADEE"}};

    if (W.Exist(vec_1, "ABCCED") == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    //====================================
    vector<string> vec_2 = {{"AAAAA"},
                            {"AAAAA"},
                            {"AAAAA"},
                            {"AAAAA"}};

    if (W.Exist(vec_2, "AAB") == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    //====================================
    vector<string> vec_3 = {{"FGABG"},
                            {"EFAEC"},
                            {"GGFBD"},
                            {"GGDCD"}};

    if (W.Exist(vec_3, "FEGGGDCDDCGBAG") == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    //====================================
    vector<string> vec_4 = {{"FCDFFD"},
                            {"BGCBFC"}};

    if (W.Exist(vec_4, "FBGCDCBFFF") == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

Output

Yes
No
Yes
Yes


Copyright (c) 2019-2022, Algotree.org.
All rights reserved.