Word Search

I randomly chose to solve the Word Search challenge at LeetCode found at the following URL: https://leetcode.com/problems/word-search/

Following are the console screen captures from the Eclipse IDE for the three sample cases using the same character array:

word: ABCCED -> true

board:

A B C E

S F C S

A D E E

usedCells:

1 1 1 0

0 0 1 0

0 1 1 0

The challenge requires the exist() method to return true (word exists) or false (word does NOT exist). For testing purposes I also displayed the input word followed by the contents of the board and an auxiliary boolean array used to keep track of the letters already used in the board (“The same letter cell may not be used more than once.”).

There are 2 ‘A’s in the board. The process starts from the top left and traverses the board right and down until the word is found or the characters in the board are exhausted. The usedCells[] array illustrates the cells that were used to find the word.

The second test case follows:

word: SEE -> true

board:

A B C E

S F C S

A D E E

usedCells:

0 0 0 0

0 0 0 1

0 0 1 1

In this case after the ‘S’ at board[1][3] is selected, the algorithm first goes up and is not able to complete the word. It then tries going down and then left. All this is done with recursion.

The last test case follows:

word: ABCB -> false

board:

A B C E

S F C S

A D E E

usedCells:

0 0 0 0

0 0 0 0

0 0 0 0

Starting at either ‘A’ on the board, it is not possible to complete the search for the word “ABCB”.

The accepted solution code written in Java follows:

public class Solution {

// **** ****

static int           ROWS          = 0;

static int           COLS          = 0;

static boolean[]     usedCells     = null;

/*

*

*/

static void printUsed() {

System.out.println(“usedCells: “);

int i = 0;

for (int row = 0; row < ROWS; row++) {

for (int col = 0; col < COLS; col++) {

System.out.print((usedCells[i++] == true ? “1” : “0” )+ ” “);

}

System.out.println();

}

}

/*

*

*/

static void printBoard(char[][] board) {

if ((ROWS <= 0) || (COLS <= 0)) {

System.out.println(“printBoard <<< unexpected ROWS: ” + ROWS + ” COLS: ” + COLS);

return;

}

System.out.println(“board: “);

for (int row = 0; row < ROWS; row++) {

for (int col = 0; col < COLS; col++) {

System.out.print(board[row][col] + ” “);

}

System.out.println();

}

}

/*

* Search for the word starting at the specified position.

*/

static boolean search(char[][] board, int row, int col, String word, int i) {

//            System.out.println(“search << row: ” + row + ” col: ” + col + ” i: ” + i);

// **** for starters ****

boolean found = false;

// **** check if we are done searching for the word ****

if (i >= word.length()) {

return true;

}

// **** determine if this cell has been used ****

if (usedCells[(row * COLS) + col] == true) {

return false;

}

// **** get the character from the current cell ****

char c = word.charAt(i);

//            System.out.println(“search <<< c: ” + c);

// **** check current position ****

if (c == board[row][col]) {

// **** flag that the cell has been used ****

usedCells[(row * COLS) + col] = true;

// **** determine if we are done with the word ****

if (i == (word.length() – 1)) {

return true;

}

// **** check up (row – 1) ****

if (row > 0) {

found = search(board, row – 1, col, word, i + 1);

if (found) {

return found;

}

}

// **** check right (col + 1) ****

if (col < (COLS – 1)) {

found = search(board, row, col + 1, word, i + 1);

if (found) {

return found;

}

}

// **** check down (row + 1) ****

if (row < (ROWS – 1)) {

found = search(board, row + 1, col, word, i + 1);

if (found) {

return found;

}

}

// **** check left (col – 1) ****

if (col > 0) {

found = search(board, row, col – 1, word, i + 1);

if (found) {

return found;

}

}

// **** flag that the cell was NOT used ****

usedCells[(row * COLS) + col] = false;

}

// **** current character did not match ****

else {

found = false;

}

// **** ****

return found;

}

/*

* Search for the word in the specified board.

*/

static boolean exist(char[][] board, String word) {

// **** determine and set the board dimensions ****

ROWS = board.length;

COLS = board[0].length;

//            System.out.println(”   board.length: ” + board.length);

//            System.out.println(“board[0].length: ” + board[0].length);

//            System.out.println(”           ROWS: ” + ROWS);

//            System.out.println(”           COLS: ” + COLS);

// **** consistency checks ****

if ((ROWS <= 0) || (COLS <= 0)) {

return false;

}

if ((word == null) || (word.length() == 0)) {

return false;

}

// **** initialize the used cells array ****

usedCells = new boolean[ROWS * COLS];

// **** for starters ****

boolean found = false;

// **** loop until no more characters on the board or word is found ****

for (int row = 0; row < ROWS && !found; row++) {

for (int col = 0; col < COLS && !found; col++) {

usedCells = new boolean[ROWS * COLS];

if (word.charAt(0) == board[row][col]) {

found = search(board, row, col, word, 0);

}

}

}

// **** ****

return found;

}

/*

*

*/

public static void main(String[] args) {

String word   = “”;

char[][] board       =      {

{‘A’, ‘B’, ‘C’, ‘E’},

{‘S’, ‘F’, ‘C’, ‘S’},

{‘A’, ‘D’, ‘E’, ‘E’}

};

//            word = “ABCCED”;

//            word = “SEE”;

word = “ABCB”;

//            char[][] board       =      {

//                                              {‘a’}

//                                              };

//            word = “a”;

//            char[][] board       =      {

//                                              {‘A’, ‘B’},

//                                              {‘D’, ‘C’}

//                                              };

//            word = “ABC”;

//            word = “ABCD”;

//            word = “ABCX”;

//            word = “ABCDE”;

//            char[][] board       =      {

//                                              {‘C’, ‘A’, ‘A’},

//                                              {‘A’, ‘A’, ‘A’},

//                                              {‘A’, ‘A’, ‘B’}

//                                              };

//            word = “AAB”;

//            char[][] board       =      {

//                                              {‘A’, ‘B’, ‘C’, ‘E’},

//                                              {‘S’, ‘F’, ‘E’, ‘S’},

//                                              {‘A’, ‘D’, ‘E’, ‘E’}

//                                              };

//            word =        “ABCEFSADEESE”;

System.out.println(“word: ” + word + ” -> ” + exist(board, word));

printBoard(board);

printUsed();

}

}

In my opinion, the challenges of LeetCode seem to be more challenging that the ones found at other sites. That said; in general the description of challenges leaves many things out which in practice should be discussed with the client in order to reduce development time. That said; since developers take these challenges for fun and to learn, it is better to make mistakes on the way ;o)

If you have comments or questions regarding this post or any other entry in this blog please do not hesitate and send me a message via email. Will reply as soon as possible and will not mention your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *