212. Word Search II

Problem

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 * 10^4
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Solution (Java)

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs (board, i, j, root, res);
            }
        }
        return res;
    }
    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        char c = board[i][j];
        if (c == '#' || p.next[c - 'a'] == null) return;
        p = p.next[c - 'a'];
        if (p.word != null) {   // found one
            res.add(p.word);
            p.word = null;     // de-duplicate ie to avoid eg: board = ["a", "a"] and words = {"a"} 
                                // if we don't remove word then it gets added twice since it can be encircled twice due to the                                   //existance of duplicates
        }
        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j ,p, res); 
        if (j > 0) dfs(board, i, j - 1, p, res);
        if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
        board[i][j] = c;
    }
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
          }
          p.word = w;
        }
        return root;
    }
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
}

Solution (Javascript)

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
  if (!board.length || !board[0].length) {
    return [];
  }
  const trie = new Trie();
  for (const word of words) {
    trie.add(word);
  }
  const m = board.length;
  const n = board[0].length;
  const output = new Set();
  const visited = [...new Array(m)].map(() => new Array(n).fill(false));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (trie.startsWith(board[i][j])) {
        dfs(board, m, n, trie, board[i][j], [i, j], output, visited);
      }
    }
  }
  return [...output];
};

const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];

function dfs(board, m, n, trie, selected, [x, y], output, visited) {
  if (trie.search(selected)) {
    output.add(selected);
  }
  visited[x][y] = true;
  for (const [di, dj] of dirs) {
    const i = x + di;
    const j = y + dj;
    if (isValid(i, j, m, n) && !visited[i][j] && trie.startsWith(selected + board[i][j])) {
      dfs(board, m, n, trie, selected + board[i][j], [i, j], output, visited);
    }
  }
  visited[x][y] = false;
}

function isValid(i, j, m, n) {
  if (i < 0 || i >= m || j < 0 || j >= n) {
    return false;
  }
  return true;
}

class Node {
  constructor() {
    this.chars = {};
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  add(word) {
    let ptr = this.root;
    for (const c of word) {
      if (!(c in ptr.chars)) {
        ptr.chars[c] = new Node();
      }
      ptr = ptr.chars[c];
    }
    ptr.isWord = true;
  }

  startsWith(str) {
    let ptr = this.root;
    for (const c of str) {
      if (!(c in ptr.chars)) {
        return false;
      }
      ptr = ptr.chars[c];
    }
    return true;
  }

  search(word) {
    let ptr = this.root;
    for (const c of word) {
      if (!(c in ptr.chars)) {
        return false;
      }
      ptr = ptr.chars[c];
    }
    return ptr.isWord;
  }
}

Explain:

nope.