Intuition

Try to match the word starting from every cell, walking to neighbours that continue the word. Mark visited cells during a path and unmark on backtrack so they can be reused by other paths.

Approach

For each cell, DFS matching word[k] against the cell.
On a match, temporarily blank the cell and recurse into the 4 neighbours for word[k+1].
Restore the cell after recursing; succeed when k reaches word length.

Complexity

Time — O(m*n*4^L): each start can branch 4 ways up to the word length L.
Space — O(L): recursion depth.

Common Pitfalls

Restore the cell on backtrack, or a single cell would be permanently blocked for other paths.

Full Solution — all languages

class Solution:
    def exist(self, board, word):
        R,C=len(board),len(board[0])
        def dfs(r,c,k):
            if k==len(word): return True
            if r<0 or r>=R or c<0 or c>=C or board[r][c]!=word[k]: return False
            tmp=board[r][c]; board[r][c]="#"
            found=dfs(r+1,c,k+1) or dfs(r-1,c,k+1) or dfs(r,c+1,k+1) or dfs(r,c-1,k+1)
            board[r][c]=tmp
            return found
        for r in range(R):
            for c in range(C):
                if dfs(r,c,0): return True
        return False

import java.util.*;

class Solution {
    public boolean exist(char[][] board, String word) {
        int R=board.length,C=board[0].length; for(int r=0;r<R;r++)for(int c=0;c<C;c++)if(dfs(board,word,r,c,0))return true; return false;
    }
    boolean dfs(char[][] board,String word,int r,int c,int k){int R=board.length,C=board[0].length; if(k==word.length())return true; if(r<0||r>=R||c<0||c>=C||board[r][c]!=word.charAt(k))return false; char tmp=board[r][c];board[r][c]='#'; boolean found=dfs(board,word,r+1,c,k+1)||dfs(board,word,r-1,c,k+1)||dfs(board,word,r,c+1,k+1)||dfs(board,word,r,c-1,k+1); board[r][c]=tmp; return found;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int R=board.size(),C=board[0].size(); function<bool(int,int,int)> dfs=[&](int r,int c,int k)->bool{if(k==(int)word.size())return true;if(r<0||r>=R||c<0||c>=C||board[r][c]!=word[k])return false;char tmp=board[r][c];board[r][c]='#';bool found=dfs(r+1,c,k+1)||dfs(r-1,c,k+1)||dfs(r,c+1,k+1)||dfs(r,c-1,k+1);board[r][c]=tmp;return found;}; for(int r=0;r<R;r++)for(int c=0;c<C;c++)if(dfs(r,c,0))return true; return false;
    }
};

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const R=board.length,C=board[0].length; function dfs(r,c,k){if(k===word.length)return true;if(r<0||r>=R||c<0||c>=C||board[r][c]!==word[k])return false;const tmp=board[r][c];board[r][c]='#';const found=dfs(r+1,c,k+1)||dfs(r-1,c,k+1)||dfs(r,c+1,k+1)||dfs(r,c-1,k+1);board[r][c]=tmp;return found;} for(let r=0;r<R;r++)for(let c=0;c<C;c++)if(dfs(r,c,0))return true; return false;
};

Word Search

Example 1

Example 2

Constraints