Solution: Longest Word in Dictionary through Deleting

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #524 (Medium): Longest Word in Dictionary through Deleting

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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" d = ["ale","apple","monkey","plea"]
Output:	"apple"

Example 2:
Input:	s = "abpcplea" 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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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;
    }
};