Longest Word in Dictionary through Deleting
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
s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]"apple"Apple is longest and lexicographically smallest.
s = "programming", dictionary = ["gram", "program", "pro", "ramming"]programForm "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.
s = "competitive", dictionary = ["comp", "compete", "tie", "pete"]competeAll 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
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.