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
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 maximum length.
Complete Code:
Output:
Dictionary: [tutorial, horizon, trial, zon], Input: taucdtorgibalbhsoariazaonzaqn Longest word in dictionary by removing few characters get the input string: tutorial