algoadvance

Leetcode 524. Longest Word in Dictionary through Deleting

Problem Statement

1. Longest Word in Dictionary through Deleting

Given a string s and a string dictionary d, you need to 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.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output:
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

Clarifying Questions

1. String Contents: Are all strings composed of only lowercase English letters?
   • Yes, all strings contain only lowercase letters.
2. Dictionary Size: Is the size of the dictionary and each word in the dictionary within reasonable limits as specified by the problem constraints (size will not exceed 1,000)?
   • Yes, dictionary size and length of strings will not exceed 1,000.
3. Tie-Breaker: Can you confirm that if multiple words are valid solutions (i.e., can be formed and have the same length), we return the lexicographically smallest one?
   • Yes, we would return the lexicographically smallest string in case of ties.

Strategy

To solve this problem, we need to:

1. Iterate through each word in the dictionary.
2. Check if a given word can be formed by deleting characters from s.
3. If multiple words can be formed, track the longest one. If there is a tie, select the lexicographically smallest one.

Key steps:

• Check if a word from the dictionary can be formed by using a double pointer technique.
• Iterate through the dictionary, comparing each word based on length and lexicographical order.

Code

import java.util.*;

public class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String longestWord = "";

        for (String word : dictionary) {
            if (isSubsequence(word, s)) {
                if (word.length() > longestWord.length() ||
                    (word.length() == longestWord.length() && word.compareTo(longestWord) < 0)) {
                    longestWord = word;
                }
            }
        }

        return longestWord;
    }

    private boolean isSubsequence(String word, String s) {
        int i = 0; // Pointer for word
        int j = 0; // Pointer for s

        while (i < word.length() && j < s.length()) {
            if (word.charAt(i) == s.charAt(j)) {
                i++;
            }
            j++;
        }

        return i == word.length();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<String> dictionary = Arrays.asList("ale", "apple", "monkey", "plea");
        System.out.println(sol.findLongestWord("abpcplea", dictionary)); // Outputs: "apple"
    }
}

Time Complexity

• Checking if a word is a subsequence: O(n + m) where n is the length of word and m is the length of s.
• Iterating through all words in the dictionary: O(k), where k is the number of words in the dictionary.

Combining these complexities, the overall time complexity:

• Let L_dict be the maximum length of words in the dictionary.
• N is the length of s.
• Given k words, the complexity will be O(k * (N + L_dict)).

This works efficiently within the problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?