Trie-based Similar Word Search
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.
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:
k character mismatches with the given query.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:
dictionary that are similar to the query based on the k mismatch criterion. The order of words in the returned array does not matter.dictionary is empty, return an empty array. If the query is empty, return an empty array.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
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.
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.
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
1 <= dictionary.length <= 10^51 <= dictionary[i].length <= 20 for each word in the dictionary.1 <= query.length <= 200 <= k <= query.length'a'-'z').dictionary are unique.k mismatch criterion.k=0, and k equal to query.length.Loading editor...