Word Search

Question: 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 cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
Given word = "ABCCED", return true.

You may view the full question here.

Approach 1: The first (successful) attempt seemed to have brewed some seemingly convoluted code with logic that can be either attributed as too naive, and definitely resource expensive.

• We maintain a map of all characters and their locations in the board
• We also maintain a map of all the characters and their count, in the word we are searching for
• If the counts don’t match we immediately return false. Else we proceed with the next checks
• We need to check all possible locations where the word can start being formed
• For every possible find, we need to consider all directions in which the word can be constructed (and NOT settle for the first find)

Here’s an implementation that uses a custom class to store the location indices and that uses recursion for the checks —

//Approach 1:
//Runtime: 33ms
//Memory usage: 41.1MB
class Solution {
    HashMap<Character, List<Location>> map = new HashMap();
    
    public boolean exist(char[][] board, String word) {
        map = new HashMap();
        char[] chars = word.toCharArray();
        if(tallyCount(board, chars)){
            List<Location> possibleStarts = map.get(chars[0]);
            if(chars.length>1){
                return check(board, chars, 0, possibleStarts);
            } else {
                return true;
            }
        }
        return false;
    }
    
   private boolean check(char[][] board, char[] word, int currI, List<Location> starts) {
     for(Location start : starts){
            char[][] copyOfBoard = makeCopy(board);
            copyOfBoard[start.r][start.c] = '*';
            List<Location> possibleNextStarts = isNeighbour(copyOfBoard, start, word[currI+1]);
            if(possibleNextStarts!=null && possibleNextStarts.size()>0){
             if(currI+1==word.length-1) {
              return true;
             } else if(check(copyOfBoard, word, currI+1, possibleNextStarts)) {
              return true;
             }
            }
        }
        return false;
    }
    
    private List<Location> isNeighbour(char[][] board, Location curr, char nextChar){
        List<Location> possibleNextL = new ArrayList();
        if(curr.c+1<board[0].length && board[curr.r][curr.c+1]==nextChar) {
            //Right
            possibleNextL.add(new Location(curr.r, curr.c+1));
        }
        if(curr.c-1>=0 && board[curr.r][curr.c-1]==nextChar){
            //Left
            possibleNextL.add(new Location(curr.r, curr.c-1));
        } 
        if(curr.r-1>=0 && board[curr.r-1][curr.c]==nextChar){
            //Top
            possibleNextL.add(new Location(curr.r-1, curr.c));
        } 
        if(curr.r+1<board.length && board[curr.r+1][curr.c]==nextChar){
            //Bottom
            possibleNextL.add(new Location(curr.r+1, curr.c));
        }
        return possibleNextL;
    }
    
    private char[][] makeCopy(char[][] board){
        char[][] copy = new char[board.length][board[0].length];
        for(int i = 0; i<board.length; i++){
            for(int j = 0; j<board[0].length; j++){
                copy[i][j] = board[i][j];
            }
        }
        return copy;
    }
    
    private boolean tallyCount(char[][] board, char[] chars){
        for(int i = 0; i<board.length; i++){
            for(int j = 0; j<board[0].length; j++){
                List<Location> locs = new ArrayList();
                if(map.containsKey(board[i][j])){
                    locs = map.get(board[i][j]);
                }
                locs.add(new Location(i, j));
                map.put(board[i][j], locs);
            }
        }
        HashMap<Character, Integer> m = new HashMap();
        for(char c : chars){
            int count = 0;
            if(m.containsKey(c)){
                count = m.get(c);
            }
            m.put(c, count+1);
        }
        for(char k : m.keySet()){
            if(!map.containsKey(k) || map.get(k).size()<m.get(k)){
                return false;
            }
        }
        return true;
    }
    
    private class Location {
        int r;
        int c;
        Location(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}

Find more posts here.

Cheers & Chao!