Word Search: Given an m x n grid of characters board and a string word, return true if word exists in the grid.

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

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Try this Problem on your own or check similar problems:

1. Remove Duplicates from Sorted Array II
2. Word Search II

Solution:

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; ++i){
            for(int j = 0; j < board[0].length; ++j){
                if(helper(board, i, j, 0, word)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean helper(char[][] board, int x, int y, int index, String word){
        if(index == word.length()) return true;
        if(x < 0 || x == board.length || y < 0 || y == board[0].length || board[x][y] != word.charAt(index)){
            return false;
        }

        board[x][y] = '#';

        boolean exist = helper(board, x + 1, y, index + 1, word) ||
                   helper(board, x, y + 1, index + 1, word) ||
                   helper(board, x - 1, y, index + 1, word) ||
                   helper(board, x, y - 1, index + 1, word);

        board[x][y] = word.charAt(index);
        return exist;
    }
}

Time/Space Complexity:

• Time Complexity: O(mn4^L)
• Space Complexity: O(L)

Explanation:

This is a standard DFS search in matrix with backtracking, the space complexity is the recursion stack where depth is equal to the length of the word L and at each level we have 4 directions to choose from (breadth/width of the recursions tree). The time complexity is O(m*n*4^L), the complexity for matrix traversal times the operation we do with each element in the matrix, in our case it’s the recursive helper operation which goes L in depth and 4 in breadth. So how do we solve this problem? We traverse the matrix starting for a good position (matching our first letter) and then we check if we can form the word from the grid adjacent characters. We have two base cases:

• Base case - when index is equal to the word length which means we found our word and we return true.
• When the current position is out-of-boundary or the character at the current position doesn’t match the character at current word index, so we return false.

We use special character # to mark the visited position in matrix and then check for the next index in the word (by moving down, right, up or left), if any of those scenario works out exist will be true, otherwise it will be false, so we can just return it as result of our helper operation. Before we do that, we must restore the value of the current position to its previous value (character at current index) essentially performing backtracking.