Word Search [LeetCode] - Other approaches than Depth-First Search

Has anyone tried out this problem on LeetCode?

I tried out this problem recalling @michael.mroczka 's workshop involving the number of islands in a 2D array, as it’s very similar here. Basically, using depth-first search except iterating over a string at the same time. However, while I did manage to derive a solution, my time limit exceeded, and I was wondering if there’s another way to implement it.

We do have this as one of the past solutions I think a past Pathrise fellow wrote over a year ago:

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || word == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        boolean[][] flag = new boolean[board.length][board[0].length]; 
        boolean result = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) != board[i][j]) {
                    continue;
                }
                flag[i][j] = true;
                result = result || helper(board, word, 1, i-1, j, flag);
                result = result || helper(board, word, 1, i+1, j, flag);
                result = result || helper(board, word, 1, i, j-1, flag);
                result = result || helper(board, word, 1, i, j+1, flag);
                flag[i][j] = false;
            }
        }
        return result;
    }
    
    public boolean helper(char[][] board, String word, int pos, int m, int n, boolean[][] flag) {
        if (pos == word.length()) {
            return true;
        }
        if (m < 0 || n < 0 || m >= board.length || n >= board[0].length) {
            return false;
        }
        if (flag[m][n] || board[m][n] != word.charAt(pos)) {
            return false;
        }
        boolean ret = false;
        flag[m][n] = true;
        ret = ret || helper(board, word, pos + 1, m - 1, n, flag);
        ret = ret || helper(board, word, pos + 1, m + 1, n, flag);
        ret = ret || helper(board, word, pos + 1, m, n - 1, flag);
        ret = ret || helper(board, word, pos + 1, m, n + 1, flag);
        flag[m][n] = false;
        return ret;
    }
}

Except I’m not entirely sure about lines 13 to 18, and lines 35 to 40. Anyone would like to pitch in?

Actually, if I look here:

I think I finally have a better understanding on what’s going on. This is something like backtracking, if I’m not mistaken. My code has a “Time Limit Exceeded” because in every call to DFS, I perform a deep copy of a hashset containing coordinates as ArrayList instances.

Your solution is almost there Gregory! And no, I don’t think the reason you mentioned is the reason for your TLE error.

You are missing a small case in your code, where you replace flag[m][n] = false; before returning ret (I don’t see the line numbers, but it’s around the end). But in this case, you should actually check first if ret is True or not. If ret is True, you can return it immediately without replacing flag[m][n] as False (This means that you avoid doing subsequent DFS calls, since you’ve already found a match.). It’s a tricky condition to miss! :space_invader:

I modified a couple of lines of code in your solution at the end, and the solution passes in 5ms, faster than ~50% of Java solution!

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || word == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        boolean[][] flag = new boolean[board.length][board[0].length]; 
        boolean result = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) != board[i][j]) {
                    continue;
                }
                flag[i][j] = true;
                result = result || helper(board, word, 1, i-1, j, flag);
                result = result || helper(board, word, 1, i+1, j, flag);
                result = result || helper(board, word, 1, i, j-1, flag);
                result = result || helper(board, word, 1, i, j+1, flag);
                flag[i][j] = false;
            }
        }
        return result;
    }
    
    public boolean helper(char[][] board, String word, int pos, int m, int n, boolean[][] flag) {
        if (pos == word.length()) {
            return true;
        }
        if (m < 0 || n < 0 || m >= board.length || n >= board[0].length) {
            return false;
        }
        if (flag[m][n] || board[m][n] != word.charAt(pos)) {
            return false;
        }
        boolean ret = false;
        flag[m][n] = true;
        ret = ret || helper(board, word, pos + 1, m - 1, n, flag);
        ret = ret || helper(board, word, pos + 1, m + 1, n, flag);
        ret = ret || helper(board, word, pos + 1, m, n - 1, flag);
        ret = ret || helper(board, word, pos + 1, m, n + 1, flag);
        
// OBSERVE Change here
        if (ret==true){
            return ret;    
        }
        flag[m][n] = false;
        return ret;
    }
}

The code above isn’t actually mine.

This is the code I have:

class Solution {
    public boolean dfs(char[][] board, HashSet<ArrayList<Integer>> visited, String word, int rowIndex, int columnIndex, int wordCharIndex) {
        if (rowIndex < 0 || rowIndex >= board.length || columnIndex < 0 || columnIndex >= board[0].length) 
            return false;
        
        System.out.println(word.charAt(wordCharIndex) + " " + wordCharIndex + " " + rowIndex + " " + columnIndex);
        
        ArrayList<Integer> newVisitedLocation = new ArrayList<Integer>();
        newVisitedLocation.add(rowIndex);
        newVisitedLocation.add(columnIndex);
        
        if (visited.contains(newVisitedLocation)) return false;
        
        if (board[rowIndex][columnIndex] == word.charAt(wordCharIndex)) {
            System.out.println("Character match! " + board[rowIndex][columnIndex]);
            if (wordCharIndex == word.length() - 1) return true;
            visited.add(newVisitedLocation);
            
            return dfs(board, ((HashSet<ArrayList<Integer>>)visited.clone()), word, rowIndex - 1, columnIndex, wordCharIndex + 1) ||
                dfs(board, ((HashSet<ArrayList<Integer>>)visited.clone()), word, rowIndex + 1, columnIndex, wordCharIndex + 1) ||
                dfs(board, ((HashSet<ArrayList<Integer>>)visited.clone()), word, rowIndex, columnIndex - 1, wordCharIndex + 1) ||
                dfs(board, ((HashSet<ArrayList<Integer>>)visited.clone()), word, rowIndex, columnIndex + 1, wordCharIndex + 1);
        } else 
            return false;
    }
    
    public boolean exist(char[][] board, String word) {
        
        HashSet<ArrayList<Integer>> resultingVisitedLocations = new HashSet<ArrayList<Integer>>();
        for (int rowIndex = 0; rowIndex < board.length; rowIndex++)
            for (int colIndex = 0; colIndex < board[rowIndex].length; colIndex++) {
                if (board[rowIndex][colIndex] == word.charAt(0) && 
                    dfs(board, resultingVisitedLocations, word, rowIndex, colIndex, 0)) return true;
                System.out.println(resultingVisitedLocations);
                resultingVisitedLocations.clear();
            }
        
        return false;
    }
}

I get a TLE because I’m performing deep copies of my hashset of coordinates, where the latency increases as I store more coordinates in them.

I took a look at the solution above again through a post I made on two different Slack workspaces, and they say that this is something along the lines of backtracking where if all cases fail, then reject this position.