DFS + Hashmap.

Search for every four directions to see if the letter could match the word. If true, go into that direction. Else track back to go to the other directions. We also need a hash map to check cycles, for every letter in the letter board can only be used once.


class Solution {
public:
        int rowLength = 0;
        int colLength = 0;
        bool pathMap[100][100];
    
        bool DFS(vector<vector<char>>& board, string &word, int i, int j, int wi)
        {
                if(wi == word.length()) return true;
                if(i < 0 || i >= rowLength || j < 0 || j >= colLength) return false;
                if(pathMap[i][j]) return false;
                if(board[i][j] != word[wi]) return false;
        
                pathMap[i][j] = true;
        
                if(DFS(board, word, i + 1, j, wi + 1)) return true;
                if(DFS(board, word, i - 1, j, wi + 1)) return true;
                if(DFS(board, word, i, j + 1, wi + 1)) return true;
                if(DFS(board, word, i, j - 1, wi + 1)) return true;
        
                pathMap[i][j] = false;
        
                return false;
        }
    
        bool exist(vector<vector<char>>& board, string word) {
                rowLength = board.size();
                if(rowLength == 0) return false;
                colLength = board[0].size();
        
                for(int i = 0; i < rowLength; ++i)
                {
                        for(int j = 0; j < colLength; ++j)
                        {
                                if(word[0] == board[i][j])
                                if(DFS(board, word, i, j, 0)) return true;
                        }
                }
                return false;
        }
};
16ms

Leave a Reply

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