Frontend School

Trie-based Similar Word Search

DSA
hard

Trie-based Similar Word Search

Hard
Trie
String Manipulation
Depth-First Search

Overview

Oracle's cloud infrastructure services often involve managing vast amounts of data, including object names, resource tags, and log entries. Efficiently searching and auto-completing these identifiers, especially when users might introduce minor typos, is crucial for productivity and reliability. This problem challenges you to implement a fuzzy search capability that can suggest relevant terms even with slight deviations from the exact query.

What you need to do / Task

Implement the function findSimilarWords that, given a dictionary of valid words and a search query, identifies all words from the dictionary that are "similar" to the query. A word is considered similar if it has the exact same length as the query and can be matched to the query with at most k character mismatches (substitutions).

Specifically, your task is to:

  1. Construct an efficient data structure (a Trie) to store the dictionary words for fast lookups.
  2. Implement a search algorithm that traverses this structure to find all words that have at most k character mismatches with the given query.
  3. Return these similar words as an array of strings.

Input & output

Function Signature: function findSimilarWords(dictionary: string[], query: string, k: number): string[]

Parameters:

  • dictionary: An array of unique strings representing the valid words. All words consist of lowercase English letters.
  • query: A string representing the search query. Consists of lowercase English letters.
  • k: An integer representing the maximum allowed character mismatches.

Return Value:

  • An array of strings, containing all words from the dictionary that are similar to the query based on the k mismatch criterion. The order of words in the returned array does not matter.

Clarifications

  • Empty dictionary/query: If the dictionary is empty, return an empty array. If the query is empty, return an empty array.
  • Definition of "mismatch": A word W from the dictionary is similar to query if len(W) == len(query) and the number of positions i where W[i] != query[i] is less than or equal to k. Only character substitutions count as mismatches; insertions or deletions are not considered for similarity in this problem.

Examples

1

Example 1

Input:

dictionary = ["apple", "apply", "apricot", "banana"], query = "aplle", k = 1

Output:

["apple"]

Note:

"apple" differs from "aplle" by one character ('p' vs 'l' at index 2). "apply" differs by two. "apricot" and "banana" are of different lengths.

2

Example 2

Input:

dictionary = ["cat", "bat", "cot", "cut", "dog"], query = "cap", k = 1

Output:

["cat"]

Note:

"cat" differs from "cap" by one character ('t' vs 'p' at index 2). "bat", "cot", "cut", "dog" all have more than one mismatch or are of different lengths.

3

Example 3

Input:

dictionary = ["test", "tent", "rent", "rest"], query = "tost", k = 2

Output:

["test", "tent", "rest"]

Note:

"test" (1 mismatch), "tent" (2 mismatches), "rest" (2 mismatches) are within the k=2 limit. "rent" has 3 mismatches.

Constraints

Constraints & assumptions

  • 1 <= dictionary.length <= 10^5
  • 1 <= dictionary[i].length <= 20 for each word in the dictionary.
  • 1 <= query.length <= 20
  • 0 <= k <= query.length
  • All words consist of lowercase English letters ('a'-'z').
  • All words in dictionary are unique.
  • The returned array of words should not contain duplicates.

Out of scope

  • Handling uppercase letters, numbers, or special characters.
  • Implementing a full-fledged edit distance (Levenshtein) algorithm. The problem strictly defines similarity based on character substitutions for words of the same length.

What interviewers evaluate

  • Correctness: The solution correctly identifies all similar words according to the k mismatch criterion.
  • Efficiency: Optimal use of a Trie for dictionary storage and search, demonstrating understanding of its time and space complexities.
  • Code Quality: Clean, readable, and well-structured code with appropriate data structures and algorithms.
  • Edge Cases: Proper handling of empty inputs, k=0, and k equal to query.length.

Loading editor...