Spell Correction using Trie and Levenshtein Distance

In this problem, you are given two lists of words: one list may contain misspelled words and the other is a dictionary of correctly spelled words. Your task is to correct each word from the first list by replacing it with the dictionary word that has the minimum Levenshtein distance (the minimum number of single-character edits required to change one word into the other). If the word appears exactly in the dictionary, leave it unchanged. The problem suggests using a Trie data structure to efficiently check whether a word is correctly spelled.

Recall that the Levenshtein distance between two strings (s) and (t) is defined by the recurrence:
[ dp[i][j] = \begin{cases} j & \text{if } i=0, \ i & \text{if } j=0, \ dp[i-1][j-1] & \text{if } s[i-1] = t[j-1], \ 1 + \min{ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] } & \text{otherwise.} ]

inputFormat

The input is read from standard input and has the following format:

1. An integer (n) representing the number of words to check.
2. (n) lines, each containing a single word (possibly misspelled).
3. An integer (m) representing the number of words in the dictionary.
4. (m) lines, each containing a correctly spelled word.

All words consist of lowercase English letters.

outputFormat

Print the corrected list of words in one line, separated by a single space. The correction is done by replacing any misspelled word (i.e. a word that does not exactly match any word in the dictionary) with the dictionary word that has the minimum Levenshtein distance to it. If the dictionary is empty or no correction is found, output the original word.## sample

2
apple
banana
3
apple
banana
cherry

apple banana