Algorithm


Problem Name: 212. Word Search II

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.

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct node_s {
    struct node_s *child[26];
    char *word;
} node_t;

typedef struct {
    char **p;
    int n;
    int sz;
} res_t;

void add2res(res_t *res, char *word) {
    if (res->sz == 0) {
        res->sz = 10;
    } else if (res->sz == res->n) {
        res->sz *= 2;
    }
    res->p = realloc(res->p, res->sz * sizeof(char *));
    //assert(res->p);
    res->p[res->n ++] = word;
}

void add2trie(node_t *node, char *word) {
    node_t *t;
    char *p = word;
    int k;
    while (*p) {
        k = *p - 'a';
        t = node->child[k];
        if (!t) {
            t = calloc(1, sizeof(node_t));
            //assert(t);
            node->child[k] = t;
        }
        node = t;
        p ++;
    }
    node->word = word;
}

void free_trie(node_t *node) {
    int i;
    node_t *t;
    for (i = 0; i  <  26; i ++) {
        t = node->child[i];
        if (t) {
            free_trie(t);
        }
    }
    free(node);
}

void dfs(char **board, int rowsz, int colsz, int x, int y, node_t *node, res_t *res) {
    char c;
    node_t *t;
    int i, j, k;
    const int offset[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    c = board[x][y];
    
    // already visited
    if (c == '.') return;
    
    t = node->child[c - 'a'];

    // not a match
    if (!t) return;
    
    // found a match
    node = t;
    
    if (node->word) {
        add2res(res, node->word);
        node->word = NULL;          // done with this word
    }
    
    board[x][y] = '.';
    
    for (k = 0; k  <  4; k ++) {
        i = x + offset[k][0];
        j = y + offset[k][1];
        
        if (i >= 0 && i  <  rowsz && j >= 0 && j < colsz) {
            dfs(board, rowsz, colsz, i, j, node, res);
        }
    }
    
    board[x][y] = c;
}

char** findWords(char** board, int boardRowSize, int boardColSize, char** words, int wordsSize, int* returnSize) {
    res_t res = { 0 };
    node_t *root;
    int i, j;
    
    root = calloc(1, sizeof(node_t));
    //assert(root);
    
    // build trie
    for (i = 0; i  <  wordsSize; i ++) {
        add2trie(root, words[i]);
    }
    
    // search
    for (i = 0; i  <  boardRowSize; i ++) {
        for (j = 0; j  <  boardColSize; j ++) {
            dfs(board, boardRowSize, boardColSize, i, j, root, &res);
        }
    }
    
    // free trie
    free_trie(root);
    
    *returnSize = res.n;
    return res.p;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output

x
+
cmd
["eat","oath"]

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector < string>& words) {
        vector<string>res;
        unordered_map 0)
                    for(auto x: m[board[i][j]]){
                        bool found = false;
                        backtrack(board, 1, i, j, board.size(), board[0].size(), x, found);
                        if(found && find(res.begin(), res.end(), x) == res.end()) res.push_back(x);
                    } 
        return res;
    }
    
    void backtrack(vector<vector < char>>& board, int pos, int r, int c, int m, int n, string& word, bool& found){
        if(board[r][c] == '0' || found) return;
        if(pos == word.size()>{
            found = true;
            return;
        }
        char tmp = board[r][c];
        board[r][c] = '0';
        if(r - 1 >= 0 && board[r - 1][c] == word[pos]) backtrack(board, pos + 1, r - 1, c, m, n, word, found);
        if(r + 1 < m  && board[r + 1][c] == word[pos]) backtrack(board, pos + 1, r + 1, c, m, n, word, found);
        if(c + 1  <  n  && board[r][c + 1] == word[pos]) backtrack(board, pos + 1, r, c + 1, m, n, word, found>;
        if(c - 1 >= 0 && board[r][c - 1] == word[pos]) backtrack(board, pos + 1, r, c - 1, m, n, word, found);
        board[r][c] = tmp;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output

x
+
cmd
["eat","oath"]

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  
  private final int[][] DIRS = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
  
  public List < String> findWords(char[][] board, String[] words) {
    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;
    }
    List < String> result = new ArrayList<>();
    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, result, board);
        }
      }
    }
    return result;
  }
  
  private void backtracking(int row, int col, TrieNode parent, List < String> result, char[][] board) {
    char letter = board[row][col];
    TrieNode currNode = parent.children.get(letter);
    if (currNode.word != null) {
      result.add(currNode.word);
      currNode.word = null;
    }
    board[row][col] = '#';
    for (int[] dir : DIRS) {
      int newRow = row + dir[0];
      int newCol = col + dir[1];
      if (newRow  <  0 || newRow >= board.length || newCol < 0 || newCol >= board[0].length) {
        continue;
      }
      if (currNode.children.containsKey(board[newRow][newCol])) {
        backtracking(newRow, newCol, currNode, result, board);
      }
    }
    board[row][col] = letter;
    if (currNode.children.isEmpty()) {
      parent.children.remove(letter);
    }
  }
  
  private class TrieNode {
    Map < Character, TrieNode> children = new HashMap();
    String word = null;
    public TrieNode() {}
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

x
+
cmd
[]

#4 Code Example with Javascript Programming

Code - Javascript Programming


class Trie {
  constructor() {
    this.word = null
    this.children = new Map()
  }
  add(word) {
    let cur = this
    for (let i = 0; i  <  word.length; i++) {
      if (!cur.children.has(word[i])) {
        cur.children.set(word[i], new Trie())
      }
      cur = cur.children.get(word[i])
    }
    cur.word = word
  }
  addArr(words) {
    words.forEach(word => this.add(word))
  }
}

const findWords = function(board, words) {
  const trie = new Trie()
  trie.addArr(words)
  const results = []
  const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
  for (let i = 0; i  <  board.length; i++) {
    for (let j = 0; j  <  board[0].length; j++) {
      dfs(board, i, j, trie, results, dirs)
    }
  }
  return results
}

const dfs = (board, i, j, trie, results, dirs) => {
  if(i < 0 || j < 0 || i >= board.length || j >= board[0].length) return
  const char = board[i][j]
  if (!trie.children.has(char)) return

  const nextTrie = trie.children.get(char)
  if (nextTrie.word) {
    results.push(nextTrie.word)
    nextTrie.word = null
  }
  
  for(let dir of dirs) {
    board[i][j] = '#'
    dfs(board, i + dir[0], j + dir[1], nextTrie, results, dirs)
    board[i][j] = char
  }
  
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

x
+
cmd
[]

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def findWords(self, board, words):
        def explore(i, j, cur):
            visited[i][j] = 0
            if "#" in cur and cur["#"] not in res_set: res.append(cur["#"]); res_set.add(cur["#"])
            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
                if 0 <= x < m and 0 <= y < n and board[x][y] in cur and visited[x][y] == -1: explore(x, y, trie[cur[board[x][y]]])
            visited[i][j] = -1
        trie, cnt, m, n, res, res_set = {}, 1, len(board), len(board and board[0]), [], set()
        visited, trie[0] = [[-1] * n for _ in range(m)], {}
        for w in words:
            cur = trie[0]
            for c in w:
                if c not in cur: trie[cnt], cur[c], cnt = {}, cnt, cnt + 1
                cur = trie[cur[c]]
            cur["#"] = w
        for i in range(m):
            for j in range(n):
                if board[i][j] in trie[0]: explore(i, j, trie[trie[0][board[i][j]]])
        return res
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

x
+
cmd
[]

#6 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0212_WordSearchII
    {
        public IList < string> FindWords(char[][] board, string[] words)
        {
            var result = new List();
            var root = BuildTrie(words);
            var N = board.Length;
            var M = board[0].Length;

            for (int i = 0; i  <  N; i++)
                for (int j = 0; j  <  M; j++)
                    BackTracking(board, i, j, N, M, root, result);

            return result;
        }

        private void BackTracking(char[][] board, int i, int j, int N, int M, TrieNode node, IList < string> results)
        {
            var ch = board[i][j];
            if (ch == '#' || node.Children[ch - 'a'] == null) return;
            node = node.Children[ch - 'a'];
            if (node.IsFinished)
            {
                results.Add(node.Word);
                node.IsFinished = false;
            }

            board[i][j] = '#';
            if (i > 0) BackTracking(board, i - 1, j, N, M, node, results);
            if (j > 0) BackTracking(board, i, j - 1, N, M, node, results);
            if (i  <  N - 1) BackTracking(board, i + 1, j, N, M, node, results);
            if (j < M - 1) BackTracking(board, i, j + 1, N, M, node, results);
            board[i][j] = ch;
        }

        private TrieNode BuildTrie(string[] words)
        {
            var root = new TrieNode();

            foreach (var word in words)
            {
                var currentNode = root;
                foreach (var ch in word)
                {
                    if (currentNode.Children[ch - 'a'] == null)
                        currentNode.Children[ch - 'a'] = new TrieNode();
                    currentNode = currentNode.Children[ch - 'a'];
                }
                currentNode.IsFinished = true;
                currentNode.Word = word;
            }

            return root;
        }

        public class TrieNode
        {
            public TrieNode[] Children { get; } = new TrieNode[26];
            public bool IsFinished { get; set; }
            public string Word { get; set; }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

x
+
cmd
[]
Advertisements

Demonstration


Previous
#211 Leetcode Design Add and Search Words Data Structure Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#213 Leetcode House Robber II Solution in C, C++, Java, JavaScript, Python, C# Leetcode