LeetCode - Word Search II

Problem description

description

Given a 2D board and a list of words from the dictionary, find all words in the board.

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

Example:

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"]

Note:

• All inputs are consist of lowercase letters a-z.
• The values of words are distinct.

Analysis

The basic idea is to use Trie. And I use the matrix to build a Trie, which needs a lot of memory.

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        
        int max = 0;
        
        for (String word:words){
            max = Math.max(max, word.length());
        }
        
        constructTrie(board, root , max);
        
        List<String> res = new ArrayList<>();
        
        for (String word:words){
            if (search(word, root)){
                res.add(word);
            }
        }
        
        return res;
    }
    
    void constructTrie(char[][] board, Node root, int maxDepth){
        for(int i = 0; i< board.length; i++){
            for (int j = 0; j< board[0].length; j++){
                boolean[][] visited = new boolean[board.length][board[0].length];
                dfs(board, i, j, root, maxDepth, visited);
            }
        }
    }
    
    int[][] dir = new int[][]{ {1,0},{0,1},{-1,0},{0,-1} };
    
    void dfs(char[][] board, int i, int j, Node node, int left, boolean[][] visited){
        if (left == 0 || i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j])
        {
            node.isEnd = true;
            return;
        }
        
        visited[i][j] = true;
        
        char c = board[i][j];
        if (node.children[c-'a'] == null){
            node.children[c-'a'] = new Node();
        }
        
        for (int[] d:dir){
            dfs(board, i+d[0], j+d[1], node.children[c-'a'], left-1, visited);
        }
        visited[i][j] = false;
    }
    
    boolean search(String word, Node root){
        Node p = root;
        
        for (char c:word.toCharArray()){
            if (p.children[c-'a'] != null){
                p = p.children[c-'a'];
            }
            else {
                return false;
            }
        }
        
        return true;
    }
    
    
    class Node{
        Node[] children = new Node[26];
        boolean isEnd = false;
    }
}

We can use the words to build a Trie and use less memory.

class TrieNode {
  HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
  String word = null;
  public TrieNode() {}
}

class Solution {
  char[][] _board = null;
  ArrayList<String> _result = new ArrayList<String>();

  public List<String> findWords(char[][] board, String[] words) {

    // Step 1). Construct the Trie
    TrieNode root = new TrieNode();
    for (String word : words) {
      TrieNode node = root;

      for (Character letter : word.toCharArray()) {
        if (node.children.containsKey(letter)) {
          node = node.children.get(letter);
        } else {
          TrieNode newNode = new TrieNode();
          node.children.put(letter, newNode);
          node = newNode;
        }
      }
      node.word = word;  // store words in Trie
    }

    this._board = board;
    // Step 2). Backtracking starting for each cell in the board
    for (int row = 0; row < board.length; ++row) {
      for (int col = 0; col < board[row].length; ++col) {
        if (root.children.containsKey(board[row][col])) {
          backtracking(row, col, root);
        }
      }
    }

    return this._result;
  }
  
  private void backtracking(int row, int col, TrieNode parent) {
    Character letter = this._board[row][col];
    TrieNode currNode = parent.children.get(letter);

    // check if there is any match
    if (currNode.word != null) {
      this._result.add(currNode.word);
      currNode.word = null;
    }

    // mark the current letter before the EXPLORATION
    this._board[row][col] = '#';

    // explore neighbor cells in around-clock directions: up, right, down, left
    int[] rowOffset = {-1, 0, 1, 0};
    int[] colOffset = {0, 1, 0, -1};
    for (int i = 0; i < 4; ++i) {
      int newRow = row + rowOffset[i];
      int newCol = col + colOffset[i];
      if (newRow < 0 || newRow >= this._board.length || newCol < 0
          || newCol >= this._board[0].length) {
        continue;
      }
      if (currNode.children.containsKey(this._board[newRow][newCol])) {
        backtracking(newRow, newCol, currNode);
      }
    }

    // End of EXPLORATION, restore the original letter in the board.
    this._board[row][col] = letter;

    // Optimization: incrementally remove the leaf nodes
    if (currNode.children.isEmpty()) {
      parent.children.remove(letter);
    }
  }
}

What to improve

• use less possible to build a Trie to save memory