252. Find Longest Word by Deleting Characters

Given a string s and a dictionary of words, return the longest word in the dictionary that can be formed by deleting some characters of s (a subsequence). If multiple have the same maximum length, return the lexicographically smallest. If none, return the empty string. Input: JSON {s, dict}.

Input: JSON {s, dict}.

Output: Quoted string — the best matching word.

Examples

Input: {"s":"abpcplea","dict":["ale","apple","monkey","plea"]}
Output: "apple"
Explanation: 'apple' is the longest subsequence.

Input: {"s":"abpcplea","dict":["a","b","c"]}
Output: "a"
Explanation: Smallest among single chars.

Input: {"s":"abc","dict":["d"]}
Output: ""
Explanation: No match.

Constraints

• 1<=s.length<=1000
• 1<=dict.length<=1000

Asked by