524. Longest Word in Dictionary through Deleting
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
iandjto traverse through the word in the dictionary and the given stringsrespectively. - While
iandjare within bounds, compare the characters at the current positions. If they match, increment both pointers. Otherwise, only incrementj. - If
ireaches the end of the word, it means the current word can be formed by deleting characters froms. Update the answer if the current word is longer or has the same length but smaller lexicographical order.
- Initialize two pointers
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.
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;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.