Longest Word Formed on Board

Given a board and a dictionary, return the longest dictionary word that can be formed by adjacent cells. If multiple words share the maximum length, return the lexicographically smallest one. Pattern focus: Word Search with Trie (Multi-Word DFS). Trie pruning keeps the search focused on dictionary paths that actually matter.

Input Format

board = character grid, words = dictionary words

Output Format

longest matched word, or empty string if none exists

Constraints

  • 1 <= rows * cols <= 10^4
  • 1 <= words.length <= 3 * 10^4
  • Board and words contain only lowercase English letters.

Examples

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

Output:

oath

Explanation:

Among the matched words, oath is the longest.

Example 2:

Input:

board = [["a"]]
words = ["b"]

Output:

Explanation:
When nothing matches the board, return the empty string.
Example 3:
Input:
board = [["a","b"],["c","d"]]
words = ["ab","abcd","acdb"]
Output:
acdb
Explanation:
Two words may tie on length, so lexicographic order decides the answer.
Loading...
Longest Word Formed on Board - Trie DSA Problem