Swiggy OA SDE Intern + Fulltime + Fresher + Experienced | CTC - 15 to 30 L | Set 2

Question

Question 1: Auto Suggest

Problem Statement

Given a dictionary consisting of N words and a query word S. You need to auto-suggest the best word from the dictionary that is closest to S.

Two words are first compared by their Levenshtein distance to the word S. If two words have the same Levenshtein distance, then the lexicographically smaller word is given priority.

Notes

 * Levenshtein distance between two strings is defined as the minimum number of edits required to obtain one string from the other. An "edit" is defined by either an insertion of a character, a deletion of a character, or a replacement of a character.

 * Examples:

   * Distance between "abc" and "ac" is 1 (deletion of b).

   * Distance between "abc" and "abd" is 1 (replacement of c to d).

   * Distance between "abc" and "abcd" is 1 (insertion of d).

 * All the words and the query word S consist of lowercase alphabets only.

Input Format

 * The first line contains a single integer N denoting the value of N (number of words in the dictionary).

 * The second line contains N space-separated strings denoting the words in the dictionary.

 * The third line contains a single string denoting the query word S.

Output Format

 * Print a single line containing the answer (the best word).

Constraints

 * * * Sample Input

5

tocor torect tocfrec tocorre tocofecd

tocorrect

 

Sample Output

tocfrec

 

Explanation

The strings belonging to the dictionary having minimum Levenshtein distance of 2 from the given string "tocorrect" are ["tocfrec", "tocorre"]. Among the two, "tocfrec" is lexicographically smaller than "tocorre". Hence, the answer is "tocfrec".