Insert all target words into a trie, then run a DFS from every cell, navigating the trie simultaneously to prune dead ends early.

Word Search II

hard

Acceptance: 37%

TrieBacktrackingMatrix

Given a two-dimensional grid of characters and a list of target words, find every word from the list that can be formed by tracing a path of horizontally or vertically adjacent cells on the grid. Each cell may be used at most once per word.

Examples

Example 1:

Input:board = [['p','q','r','s'],['t','u','v','w'],['x','y','z','a'],['b','c','d','e']], words = ['puy','quz','xyz','pqr']

Output:['pqr','xyz']

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Word Search II

Examples

Hints

Related Problems