Scale Engineer

Word Search II

Hard
#0200Time: O(N * M * 4^L) where N is the number of cells in the board, M is the number of words, and L is the maximum length of a wordSpace: O(N) where N is the size of the board for the visited array in DFS16 companies
Patterns
Backtracking
Data structures
ArrayStringTrieMatrix
Companies
AirbnbCiscoDoorDashGoogle

Prompt

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must 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 in a word.

 

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

 

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

For each word in the words list, try to find it in the board by performing DFS search starting from each cell.

Algorithm

  1. For each word in the input array:
    • For each cell in the board:
      • If the current cell matches the first character of the word:
        • Perform DFS to find the complete word
      • Mark cells as visited during DFS
      • Unmark cells when backtracking
  2. Add found words to the result set
  3. Return the list of found words

Walkthrough

This approach involves checking each word from the words list by attempting to find it on the board. For each word, we iterate through every cell on the board and try to match the word starting from that cell using DFS (Depth First Search).

class Solution {    private int m, n;    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};        public List<String> findWords(char[][] board, String[] words) {        Set<String> result = new HashSet<>();        m = board.length;        n = board[0].length;                for (String word : words) {            boolean found = false;            for (int i = 0; i < m && !found; i++) {                for (int j = 0; j < n && !found; j++) {                    if (board[i][j] == word.charAt(0)) {                        boolean[][] visited = new boolean[m][n];                        if (dfs(board, word, 0, i, j, visited)) {                            result.add(word);                            found = true;                        }                    }                }            }        }                return new ArrayList<>(result);    }        private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited) {        if (index == word.length()) return true;        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index))             return false;                    visited[i][j] = true;                for (int[] dir : directions) {            int newI = i + dir[0];            int newJ = j + dir[1];            if (dfs(board, word, index + 1, newI, newJ, visited))                 return true;        }                visited[i][j] = false;        return false;    }}

Complexity

Time

O(N * M * 4^L) where N is the number of cells in the board, M is the number of words, and L is the maximum length of a word

Space

O(N) where N is the size of the board for the visited array in DFS

Trade-offs

Pros

  • Simple to implement and understand

  • Works well for small boards and word lists

  • Low space complexity

Cons

  • Very inefficient for large word lists

  • Repeats work for words with common prefixes

  • Time complexity grows exponentially with word length

Solutions

class Trie { Trie [] children = new Trie [ 26 ]; int ref = - 1 ; public void insert ( String w , int ref ) { Trie node = this ; for ( int i = 0 ; i < w . length (); ++ i ) { int j = w . charAt ( i ) - 'a' ; if ( node . children [ j ] == null ) { node . children [ j ] = new Trie (); } node = node . children [ j ]; } node . ref = ref ; } } class Solution { private char [][] board ; private String [] words ; private List < String > ans = new ArrayList <>(); public List < String > findWords ( char [][] board , String [] words ) { this . board = board ; this . words = words ; Trie tree = new Trie (); for ( int i = 0 ; i < words . length ; ++ i ) { tree . insert ( words [ i ], i ); } int m = board . length , n = board [ 0 ]. length ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { dfs ( tree , i , j ); } } return ans ; } private void dfs ( Trie node , int i , int j ) { int idx = board [ i ][ j ] - 'a' ; if ( node . children [ idx ] == null ) { return ; } node = node . children [ idx ]; if ( node . ref != - 1 ) { ans . add ( words [ node . ref ]); node . ref = - 1 ; } char c = board [ i ][ j ]; board [ i ][ j ] = '#' ; int [] dirs = {- 1 , 0 , 1 , 0 , - 1 }; for ( int k = 0 ; k < 4 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < board . length && y >= 0 && y < board [ 0 ]. length && board [ x ][ y ] != '#' ) { dfs ( node , x , y ); } } board [ i ][ j ] = c ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem