AceYourInterviews
Checking sign-in…

91. Word Search II

AdvancedTraverse board paths and dictionary prefixes together, with path-local visited state

Find all supplied words that can be spelled by moving through orthogonally adjacent board cells. A path for one word cannot use the same coordinate twice.

Different words may reuse cells in their separate searches. Leave the board unchanged and follow the contract's uniqueness and output-order requirements.

Example 1

Input

board=[oa,ht]; words=[o,oa,oath,oath,hat,ao,oao]

Output

[ao,o,oa,oath]

Explanation: The path o→a→t→h finds oath; oa stays searchable after o is emitted. Duplicate input/path occurrences emit one word, and oao would reuse the first o.

Example 2

Input

board=[aa]; words=[a,aa,aaa,aa]

Output

[a,aa]

Explanation: Two distinct a coordinates can spell aa, but no third coordinate exists.

Example 3

Input

board=[ab,cd]; words=[ad,ac,bd]

Output

[ac,bd]

Explanation: ad would require a diagonal edge and is rejected.

Constraints

  • 0 <= rows, columns <= 12
  • 0 <= words.length <= 104
  • 1 <= words[i].length <= 144
  • sum(words[i].length) <= 105
  • Board cells and dictionary words contain lowercase English letters. Words are nonempty; no cell can be reused within one word path.
Hints
Hint 1

Several words can share one prefix, so consider a trie.

Hint 2

State must track both the dictionary prefix and the current no-reuse board path.

Hint 3

Mark on entry, consume a terminal only once, continue its descendants, and unmark on backtrack.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Shared prefixes, duplicate words, and local terminal consumption

["oa","ht"]
["o","oa","oath","oath","hat","ao","oao"]
["ao","o","oa","oath"]