|
This post is completed by 1 user
|
Add to List |
482. Largest word in dictionary by removing a few characters from the given string
Given a dictionary (list of words) and an input string K. Find the largest word in the dictionary which can be obtained by deleting a few characters in the input string K.
Example:
Dictionary: [tutorial, horizon, trial, zon] Input: taucdtorgibalbhsoariazaonzaqn Output: tutorial Dictionary: [tutorial, horizon, trial, zon], Input: attroialled Output: trial
Approach:
Please read - Given two strings, check if one string is a subsequence of another
The approach is quite simple here, iterate the dictionary, and for each word check if the word is a subsequence of the given input word, if yes then this word could be an answer. Keep track of the length word for which the above condition is true and pick the one with the maximum length.
Output:
Dictionary: [tutorial, horizon, trial, zon], Input: taucdtorgibalbhsoariazaonzaqn Longest word in dictionary by removing few characters get the input string: tutorial