Minimum Edit-Distance String for Each Query
Updated
Problem statement
You are given an array of distinct candidate strings strings and an array of query strings queries. The edit distance between two strings is the minimum number of single-character insertions, deletions, and replacements needed to transform one string into the other. Each operation costs one.
For each query, return the candidate string with minimum edit distance to that query. If several candidates have the same minimum distance, return the lexicographically smallest candidate.
Comparisons are case-sensitive and use the characters exactly as provided, without additional normalization.
Implement findClosestStrings(strings, queries).
Function
findClosestStrings(strings: String[], queries: String[]) → String[]Examples
Example 1
strings = ["cat","bat","rat"]queries = ["hat","cats"]return = ["bat","cat"]For "hat", all three candidates are one replacement away, so the lexicographically smallest, "bat", is returned. For "cats", deleting the final 's' gives "cat" in one edit.
Example 2
strings = ["Apple","apple"]queries = ["apple"]return = ["apple"]The comparison is case-sensitive, so "apple" has distance zero and is selected.
Constraints
1 <= strings.length <= 100.1 <= queries.length <= 50.- Every string has length between
1and50, inclusive. - Candidate strings are distinct.
- Strings contain printable ASCII characters.
More Target Online Assessment questions
Similar questions at other companies
- Longest String ChainVisa · OAVisa interview questions
- Sort by Variable-Length Alphabet TokensBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Longest Subsequence That Is a SubstringBooking.com · OA
- Count Proper Prefix MatchesAT&T · OAAT&T interview questions
- Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
- Decode Words with Anagram KeysCresta · OACresta interview questions
- String Permutations in Custom Character OrderWex · OA · PHONE SCREEN
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions