Medium

Words Within Two Edits of Dictionary

LAB

Return query words that differ from at least one dictionary word in at most two positions, preserving query order.

EXAMPLES

Example 1

Input
{
  "queries": [
    "word",
    "note",
    "ants",
    "wood"
  ],
  "dictionary": [
    "wood",
    "joke",
    "moat"
  ]
}

Output
[
  "word",
  "note",
  "wood"
]

FUNCTION SHAPE

queries: stringArraydictionary: stringArray→stringArray

SOLUTION NOTE

This is a simple trie application. We try all children in the trie, and when there is a mismatch while traversing the trie, we reduce the edit count by one. When the edit count is negative we return False. If we reach the end of the word with at most 2 edits, this word works. If any such children work, we return True.

Open on LeetCode ↗