Solution: Longest Word in Dictionary through Deleting
Tags: algorithms, javascript, java, python
Published: 2021-02-22 12:04:53

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/discuss/explore/february-leetcoding-challenge-2021/1077776).*

---

#### [Leetcode Problem #524 (*Medium*): Longest Word in Dictionary through Deleting](https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/)

---

#### ***Description:***
</br>
(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

---

#### ***Examples:***

>
Example 1:||
|---:|---|
Input:|s = "abpcplea"<br/>d = ["ale","apple","monkey","plea"]
Output:|"apple"
>
Example 2:||
|---:|---|
Input:|s = "abpcplea"<br/>d = ["a","b","c"]
Output:|"a"

---

#### ***Constraints:***
>
 - All the strings in the input will only contain lower-case letters.
 - The size of the dictionary won't exceed `1,000`.
 - The length of all the strings in the input won't exceed `1,000`.

---

#### ***Idea:***
</br>
(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

To avoid having to sort the dictionary (**D**), we can just keep track of our best answer (**ans**), and skip any words that would be a worse answer than the current one.

Then, we can simply check each **word** to see if we can find the **char**'s in **S** in order to make the **word**. We can use a string indexing function to good effect here, making sure to start each new **char** search from just after the position (**pos**) of the last **char** found.

If we fail to find a **char**, **break** to the next **word**. If we successfully reach the end of a **word**, we can **return** it. If we never find a valid **word** match, **return** an empty string.

---

#### ***Implementation:***

The code for all four languages is almost identical.

Java won't let you directly compare two strings with a greater/less than, so we can use **.compareTo()**.

---

#### ***Javascript Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var findLongestWord = function(S, D) {
    let ans = ""
    for (let word of D) {
        let a = word.length, b = ans.length
        if (a < b || (a === b && word > ans)) continue
        let pos = -1
        for (let char of word) {
            pos = S.indexOf(char, pos + 1)
            if (pos === -1) break
        }
        if (pos !== -1) ans = word
    }
    return ans
};
```

---

#### ***Python Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def findLongestWord(self, S: str, D: List[str]) -> str:
        ans = ""
        for word in D:
            a, b = len(word), len(ans)
            if a < b or (a == b and word > ans): continue
            pos = -1
            for char in word:
                pos = S.find(char, pos + 1)
                if pos == -1: break
            if pos != -1: ans = word
        return ans
```

---

#### ***Java Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public String findLongestWord(String S, List<String> D) {
        String ans = "";
        for (String word : D) {
            int a = word.length(), b = ans.length();
            if (a < b || (a == b && word.compareTo(ans) > 0)) continue;
            int pos = -1;
            for (int i = 0; i < a; i++) {
                pos = S.indexOf(word.charAt(i), pos + 1);
                if (pos == -1) break;
            }
            if (pos != -1) ans = word;
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    string findLongestWord(string S, vector<string>& D) {
        string ans = "";
        for (string word : D) {
            int a = word.length(), b = ans.length();
            if (a < b || (a == b && word > ans)) continue;
            int pos = -1;
            for (int i = 0; i < a; i++) {
                pos = S.find(word[i], pos + 1);
                if (pos == -1) break;
            }
            if (pos != -1) ans = word;
        }
        return ans;
    }
};
```