Description
Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some characters of s. If there are multiple, return the lexicographically smallest. If none, return empty string.
Examples
Input:
s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]Output:
"apple"Explanation:
apple is longest and lexicographically smallest.
Input:
s = "programming", dictionary = ["gram", "program", "pro", "ramming"]Output:
programExplanation:
Form "gram" (p-r-o-g-r-a-m-m-i-n-g), "program" (p-r-o-g-r-a-m-m-i-n-g), "pro" (p-r-o-g-r-a-m-m-i-n-g), and "ramming" (p-r-o-g-r-a-m-m-i-n-g) by deleting characters. "program" is the longest with 7 characters.
Input:
s = "competitive", dictionary = ["comp", "compete", "tie", "pete"]Output:
competeExplanation:
All dictionary words can be formed: "comp" (c-o-m-p-e-t-i-t-i-v-e), "compete" (c-o-m-p-e-t-i-t-i-v-e), "tie" (c-o-m-p-e-t-i-t-i-v-e), "pete" (c-o-m-p-e-t-i-t-i-v-e). "compete" is the longest with 7 characters.
Constraints
- •
1 ≤ s.length ≤ 1000 - •
1 ≤ dictionary.length ≤ 1000