Blogs Hub

by Sumit Chourasia | Nov 01, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Word Search - Array - Medium - LeetCode

Word Search - Array - Medium - LeetCode

Given a 2D board and a word, find if the 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 3:


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

Constraints:

board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

public class Solution {
    public bool Exist(char[][] board, string word) {
        
        var used = new HashSet<string>();
        for(int i=0;i<board.Length;i++){
            for(int j=0;j<board[0].Length;j++){
                if(board[i][j]==word[0]){                                     
                    var res = Helper(board,i,j, word, 0, used);  
                    if(res){
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    private bool Helper(char[][] board, int x, int y, string word,int start, HashSet<string> used){
                
        if(start == word.Length && used.Count()==word.Length){                      
            return true;
        }   
        
        if(x<0 || x>board.Length-1){
            return false;
        }
        
        if(y<0 || y > board[0].Length-1){
            return false;
        }
        
        if(start> word.Length-1){
            return false;
        }
        
        if(board[x][y]!=word[start]){
            return false;
        }
        
        if(used.Contains(GetKey(x,y))){
            return false;
        }
        
        used.Add(GetKey(x,y));
        
        bool result = false;        
        
        int x1 = x-1;
        int y1 = y;        
        result = result || Helper(board, x1, y1, word, start+1, used);
        
        x1 = x+1;
        y1 = y;        
        result = result || Helper(board, x1, y1, word, start+1, used);
        
        x1 = x;
        y1 = y-1;        
        result = result || Helper(board, x1, y1, word, start+1, used);
        
        x1 = x;
        y1 = y+1;        
        result = result || Helper(board, x1, y1, word, start+1, used);
        
        used.Remove(GetKey(x, y));
        return result;
    }
    
    private string GetKey(int x, int y){
        return x+":"+y;
    }
}

Time Complexity: O(2^n)

Space Complexity: O(n)