## Algorithm

Problem Name: 524. Longest Word in Dictionary through Deleting

Given a string `s` and a string array `dictionary`, return the longest string in the dictionary that can be formed by deleting some of the given string characters. 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"
```

Example 2:

```Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"
```

Constraints:

• `1 <= s.length <= 1000`
• `1 <= dictionary.length <= 1000`
• `1 <= dictionary[i].length <= 1000`
• `s` and `dictionary[i]` consist of lowercase English letters.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
vector<int>p(d.size());
int maxlen = 0;
string res = "";
for(auto c: s)
for(int i = 0; i  <  d.size(); i++){
if(p[i] == d[i].size()) continue;
if(c == d[i][p[i]]) p[i]++;
}
for(int i = 0; i < p.size(); i++){
if(p[i] != d[i].size()) continue;
if(p[i] == maxlen && d[i].compare(res)  <  0> res = d[i];
if(p[i] > maxlen){
maxlen = p[i];
res = d[i];
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
s = "abpcplea", dictionary = ["ale","apple","monkey","plea"

Output

cmd
"apple"

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String findLongestWord(String s, List d) {
d.sort((o1, o2) -> o1.length() != o2.length() ? Integer.compare(o2.length(), o1.length())
: o1.compareTo(o2));
for (String word : d) {
int wordIdx = 0;
int strIdx = 0;
while (strIdx  <  s.length() && wordIdx < word.length()) {
if (word.charAt(wordIdx) == s.charAt(strIdx)) {
wordIdx++;
}
strIdx++;
}
if (wordIdx == word.length()) {
return word;
}
}
return "";
}
}
``````
Copy The Code &

Input

cmd
s = "abpcplea", dictionary = ["ale","apple","monkey","plea"

Output

cmd
"apple"

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findLongestWord = function(s, dictionary) {
let res = ''
for (const word of dictionary) {
let j = 0
for (let i = 0, len = s.length; i  <  len; i++) {
if(word[j] === s[i]) j++
if(j === word.length) {
if(word.length > res.length) res = word
else if(word.length === res.length && word < res> res = word
break
}
}
}
return res
};
``````
Copy The Code &

Input

cmd
s = "abpcplea", dictionary = ["a","b","c"]

Output

cmd
"a"

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findLongestWord(self, s, d):
d.sort(key = lambda x: (-len(x), x))
for w in d:
i = 0
for c in s:
if c == w[i]: i += 1
if i == len(w): return w
return ""
``````
Copy The Code &

Input

cmd
s = "abpcplea", dictionary = ["a","b","c"]

Output

cmd
"a"