LeetCode 524: Longest Word in Dictionary through Deleting Solution

Master LeetCode problem 524 (Longest Word in Dictionary through Deleting), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

524. Longest Word in Dictionary through Deleting

Medium

Array Two Pointers String Sorting

Problem Explanation

Explanation

To solve this problem, we can iterate through the dictionary and check if each word can be formed by deleting characters from the given string s. We can achieve this by using two pointers to compare the characters of both the word in the dictionary and the given string. If a word in the dictionary can be formed by deleting characters from s, we update our answer if the current word is longer or if it has the same length but smaller lexicographical order.

Algorithm

Sort the dictionary in lexicographical order to handle the tie-breaker condition.
Iterate through each word in the dictionary and perform the following steps:
- Initialize two pointers i and j to traverse through the word in the dictionary and the given string s respectively.
- While i and j are within bounds, compare the characters at the current positions. If they match, increment both pointers. Otherwise, only increment j.
- If i reaches the end of the word, it means the current word can be formed by deleting characters from s. Update the answer if the current word is longer or has the same length but smaller lexicographical order.

Time Complexity

The time complexity of this solution is O(n * m * log m), where n is the number of words in the dictionary and m is the average length of the words in the dictionary. The sorting of the dictionary contributes to the log m factor.

Space Complexity

The space complexity is O(1) as we are using constant extra space.

Solution Code

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String result = "";
        Collections.sort(dictionary, (a, b) -> a.length() != b.length() ? b.length() - a.length() : a.compareTo(b));
        
        for (String word : dictionary) {
            int i = 0, j = 0;
            while (i < word.length() && j < s.length()) {
                if (word.charAt(i) == s.charAt(j)) {
                    i++;
                }
                j++;
            }
            
            if (i == word.length() && (word.length() > result.length() || (word.length() == result.length() && word.compareTo(result) < 0))) {
                result = word;
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 524 (Longest Word in Dictionary through Deleting)?

This page provides optimized solutions for LeetCode problem 524 (Longest Word in Dictionary through Deleting) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 524 (Longest Word in Dictionary through Deleting)?

The time complexity for LeetCode 524 (Longest Word in Dictionary through Deleting) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 524 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 524 in Java, C++, or Python.

Back to LeetCode Solutions