Word Search II

Hard
1573.

Word Search II

Word Search II is a hard coding problem on strings, matrix and backtracking, asked in Amazon, Google, Microsoft and Uber interviews.

board is an m x n grid of lowercase letters given as m strings, and words is a list of distinct lowercase words.

A word can be formed on the board if its letters can be read along a path of cells where each step moves to a horizontally or vertically adjacent cell, and no cell is used more than once in that word.

Return every word of words that can be formed, sorted in ascending lexicographic order.

Example 1

Input
board = ["code","tarx","kibo"], words = ["cod","dex","bra","kit","tack","oar","box"]
Output
["box","bra","cod","dex","oar"]
Explanation
`kit` fails because no `t` touches the `i`, and `tack` because no `c` touches the `a`.

Example 2

Input
board = ["ab","cd"], words = ["abdc","abcd","acdb"]
Output
["abdc","acdb"]
Explanation
`abcd` would need `b` next to `c`, but they touch only diagonally.

Example 3

Input
board = ["a"], words = ["aa"]
Output
[]
Explanation
A cell cannot be used twice in one word.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i] consists of lowercase English letters
  • 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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Word Search II — Solution in Python, Java & C++

Word Search II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Word Search II is a hard coding problem on strings, matrix and backtracking, asked in Amazon, Google, Microsoft and Uber interviews.

Problem statement

board is an m x n grid of lowercase letters given as m strings, and words is a list of distinct lowercase words.

A word can be formed on the board if its letters can be read along a path of cells where each step moves to a horizontally or vertically adjacent cell, and no cell is used more than once in that word.

Return every word of words that can be formed, sorted in ascending lexicographic order.

Example 1

Input: board = ["code","tarx","kibo"], words = ["cod","dex","bra","kit","tack","oar","box"]
Output: ["box","bra","cod","dex","oar"]
Explanation: `kit` fails because no `t` touches the `i`, and `tack` because no `c` touches the `a`.

Example 2

Input: board = ["ab","cd"], words = ["abdc","abcd","acdb"]
Output: ["abdc","acdb"]
Explanation: `abcd` would need `b` next to `c`, but they touch only diagonally.

Example 3

Input: board = ["a"], words = ["aa"]
Output: []
Explanation: A cell cannot be used twice in one word.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i] consists of lowercase English letters
  • 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

Hints for Word Search II

  1. Hint 1

    Searching the board once per word repeats the same work for words that share a prefix.

  2. Hint 2

    Put all the words in a trie. Then a single DFS from each cell can follow the trie and the board together.

  3. Hint 3

    During the DFS, stop as soon as the current path is not a prefix of any word; when you reach a node that ends a word, record it and clear the marker so it is reported once.

How to solve Word Search II

Walk the board and a trie of the words in lockstep: the trie tells the DFS which next letters can still lead to a word, so hopeless paths are abandoned immediately.

Approach

  1. Insert every word into a trie; store the word (or its index) at the node where it ends.
  2. From every cell, start a DFS with the trie root. At cell (r, c) move to the child for its letter; if there is none, return.
  3. If that child ends a word, add the word to the answer and clear the marker (so it is not added twice).
  4. Mark the cell as used, recurse into the four neighbours with the child node, then unmark it.
  5. Sort the answer.

Why it works

A word is found exactly when some path of distinct adjacent cells spells it, and the DFS explores every such path whose letters stay inside the trie — any path leaving the trie cannot be a prefix of a word, so pruning it loses nothing. Clearing the end marker reports each word once even if it can be formed in several ways.

Complexity

  • Time — O(m · n · 4 · 3^(L-1)) in the worst case, L = the longest word length
  • Space — O(total length of the words) for the trie

Pitfalls

  • A cell may be reused across different words, but not within one word — unmark it when backtracking.
  • Without clearing the end marker, a word that can be formed along two paths is reported twice.
  • The answer must be sorted; the DFS finds words in board order.

Reference solution

Python

from typing import List

def findWords(board: List[str], words: List[str]) -> List[str]:
    m, n = len(board), len(board[0])
    g = [list(row) for row in board]
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = w
    found = []

    def dfs(r, c, parent):
        ch = g[r][c]
        node = parent.get(ch)
        if node is None:
            return
        if '$' in node:
            found.append(node.pop('$'))
        g[r][c] = '#'
        if r > 0:
            dfs(r - 1, c, node)
        if r + 1 < m:
            dfs(r + 1, c, node)
        if c > 0:
            dfs(r, c - 1, node)
        if c + 1 < n:
            dfs(r, c + 1, node)
        g[r][c] = ch

    for r in range(m):
        for c in range(n):
            dfs(r, c, root)
    return sorted(found)

Java

public static String[] findWords(String[] board, String[] words) {
    int m = board.length, n = board[0].length();
    char[][] g = new char[m][];
    for (int i = 0; i < m; i++) g[i] = board[i].toCharArray();
    List<int[]> next = new ArrayList<>();
    List<Integer> end = new ArrayList<>();
    next.add(new int[26]);
    end.add(-1);
    for (int w = 0; w < words.length; w++) {
        int node = 0;
        for (char ch : words[w].toCharArray()) {
            int k = ch - 'a';
            if (next.get(node)[k] == 0) {
                next.add(new int[26]);
                end.add(-1);
                next.get(node)[k] = next.size() - 1;
            }
            node = next.get(node)[k];
        }
        end.set(node, w);
    }
    List<String> found = new ArrayList<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) wordDfs(g, r, c, 0, next, end, words, found);
    Collections.sort(found);
    return found.toArray(new String[0]);
}

private static void wordDfs(char[][] g, int r, int c, int parent, List<int[]> next, List<Integer> end, String[] words, List<String> found) {
    char letter = g[r][c];
    if (letter == '#') return;
    int cur = next.get(parent)[letter - 'a'];
    if (cur == 0) return;
    if (end.get(cur) >= 0) { found.add(words[end.get(cur)]); end.set(cur, -1); }
    g[r][c] = '#';
    if (r > 0) wordDfs(g, r - 1, c, cur, next, end, words, found);
    if (r + 1 < g.length) wordDfs(g, r + 1, c, cur, next, end, words, found);
    if (c > 0) wordDfs(g, r, c - 1, cur, next, end, words, found);
    if (c + 1 < g[0].length) wordDfs(g, r, c + 1, cur, next, end, words, found);
    g[r][c] = letter;
}

C++

static void wordDfs(vector<string>& g, int r, int c, int parent, vector<array<int, 26>>& nxt, vector<int>& endAt, vector<string>& words, vector<string>& found) {
    char letter = g[r][c];
    if (letter == '#') return;
    int cur = nxt[parent][letter - 'a'];
    if (cur == 0) return;
    if (endAt[cur] >= 0) { found.push_back(words[endAt[cur]]); endAt[cur] = -1; }
    g[r][c] = '#';
    if (r > 0) wordDfs(g, r - 1, c, cur, nxt, endAt, words, found);
    if (r + 1 < (int)g.size()) wordDfs(g, r + 1, c, cur, nxt, endAt, words, found);
    if (c > 0) wordDfs(g, r, c - 1, cur, nxt, endAt, words, found);
    if (c + 1 < (int)g[0].size()) wordDfs(g, r, c + 1, cur, nxt, endAt, words, found);
    g[r][c] = letter;
}

vector<string> findWords(vector<string>& board, vector<string>& words) {
    vector<string> g = board;
    vector<array<int, 26>> nxt(1);
    nxt[0].fill(0);
    vector<int> endAt(1, -1);
    for (int w = 0; w < (int)words.size(); w++) {
        int node = 0;
        for (char ch : words[w]) {
            int k = ch - 'a';
            if (nxt[node][k] == 0) {
                array<int, 26> fresh;
                fresh.fill(0);
                nxt.push_back(fresh);
                endAt.push_back(-1);
                nxt[node][k] = (int)nxt.size() - 1;
            }
            node = nxt[node][k];
        }
        endAt[node] = w;
    }
    vector<string> found;
    for (int r = 0; r < (int)g.size(); r++)
        for (int c = 0; c < (int)g[0].size(); c++) wordDfs(g, r, c, 0, nxt, endAt, words, found);
    sort(found.begin(), found.end());
    return found;
}

JavaScript

var findWords = function(board, words) {
    var m = board.length, n = board[0].length;
    var g = board.map(function(row) { return row.split(''); });
    var next = [new Array(26).fill(0)], end = [-1];
    for (var w = 0; w < words.length; w++) {
        var node = 0;
        for (var i = 0; i < words[w].length; i++) {
            var ch = words[w].charCodeAt(i) - 97;
            if (!next[node][ch]) { next.push(new Array(26).fill(0)); end.push(-1); next[node][ch] = next.length - 1; }
            node = next[node][ch];
        }
        end[node] = w;
    }
    var found = [];
    var dfs = function(r, c, parent) {
        var letter = g[r][c];
        if (letter === '#') return;
        var cur = next[parent][letter.charCodeAt(0) - 97];
        if (!cur) return;
        if (end[cur] >= 0) { found.push(words[end[cur]]); end[cur] = -1; }
        g[r][c] = '#';
        if (r > 0) dfs(r - 1, c, cur);
        if (r + 1 < m) dfs(r + 1, c, cur);
        if (c > 0) dfs(r, c - 1, cur);
        if (c + 1 < n) dfs(r, c + 1, cur);
        g[r][c] = letter;
    };
    for (var r = 0; r < m; r++) for (var c = 0; c < n; c++) dfs(r, c, 0);
    found.sort();
    return found;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Matrix and Grid Traversal