Longest Word in Dictionary through Deleting
Given a string s and a string array dictionary, return the longest string in dictionary that can be formed by deleting some characters from s.
If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1
Input
s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]Output
"apple"The word "apple" is the longest dictionary word that can be formed by deleting characters from "abpcplea".
Example 2
Input
s = "abpcplea", dictionary = ["a","b","c"]Output
"a"All three words can be formed from "abpcplea", and "a" is the lexicographically smallest among the longest valid words of length 1.
Constraints
- 1 <= s.length <= 1000
- 1 <= dictionary.length <= 1000
- 1 <= dictionary[i].length <= 1000
- s and dictionary[i] consist of lowercase English letters.