524. Longest Word in Dictionary through Deleting
Problem Description
The task is to find the longest string from a given list of words (the dictionary) that can be created by removing some of the characters from a given string s
. If you can make multiple words of the same maximum length, you should return the one that comes first alphabetically. Should there be no words from the dictionary that can be formed, the answer would be an empty string.
To solve this problem, we need to determine if a given word in the dictionary can be formed by deleting characters from the string s
. We use a two-pointer approach to compare characters of a dictionary word and the string s
without rearranging any character's order.
Intuition
The intuition behind the solution is to use a two-pointer approach that can efficiently validate whether a word from the dictionary is a subsequence of the string s
. Here's how we proceed:
- Initialize two pointers,
i
for the index in the strings
andj
for the index in the current dictionary word. - Increment
i
each time we examine a character ins
. - Increment
j
only when the characters ati
ins
andj
in the dictionary word match. - A dictionary word is a subsequence of
s
if we can traverse through the entire word (i.e.,j
equals the length of the word) by selectively matching characters ins
.
By iterating through each word in the dictionary and applying the two-pointer technique, we can check which words can be formed. During the process, we also keep track of the longest word that satisfies the condition. If multiple words have the same length, we choose the one with the lowest lexicographical order, which is the same as saying the smallest in alphabetical order.
The check
function implements the two-pointer technique, and the outer loop through the dictionary selects the best candidate word according to the above-mentioned criteria.
Learn more about Two Pointers and Sorting patterns.
Solution Approach
The solution implements a straightforward algorithm which utilizes the two-pointer pattern to match dictionary words against the string s
. Let's break down how the Solution class achieves this:
-
The
findLongestWord
function is where we start, and it takes a strings
and a list of stringsdictionary
as inputs. -
It defines an inner function
check
that takes two stringsa
(the given strings
) andb
(a word from the dictionary). This function uses the two-pointer technique to determine ifb
can be formed froma
by deletion of characters.- It starts with two indexes,
i
at 0 for stringa
andj
at 0 for stringb
. - It iterates over the characters in
a
usingi
and only movesj
forward if the characters ata[i]
andb[j]
match. - If
j
reaches the length of the stringb
, it meansb
is a subsequence ofa
, andcheck
returnsTrue
.
- It starts with two indexes,
-
After the
check
function, we have a variableans
which is initialized to an empty string. This will hold the longest string from the dictionary that can be formed. -
The solution iterates over each word in the
dictionary
:- Using the
check
function, it verifies if the current word can be formed froms
. - If it can, it then checks if the current word is longer than the one stored in
ans
or if it is the same length but lexicographically smaller. - If either condition is met, we update
ans
with the current word.
- Using the
-
After checking all words in the dictionary, the solution returns
ans
, which contains the longest word that can be formed by deleting some of the given string characters, or the smallest one in lexicographical order in case there are multiple.
The use of the two-pointer technique is a key aspect of this solution as it allows for an efficient check without the need to create additional data structures or perform unnecessary computations. It is a common pattern when you need to compare or match sequences without altering their order.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Assume we have the following:
s = "abpcplea"
dictionary = ["ale", "apple", "monkey", "plea"]
The goal is to find the longest word from dictionary
that can be formed by deleting some characters in s
.
According to our algorithm:
-
Start by iterating over each word in the dictionary. Initialize
ans = ""
. -
For each word in the dictionary:
- Call the
check
function to determine if the word can be formed froms
.
- Call the
-
Let's start with the word
"ale"
:- Initialize two pointers,
i = 0
fors
andj = 0
for"ale"
. - Traverse
s
from left to right usingi
and compare withj
on"ale"
- Characters match at
s[0] = "a"
and"ale"[0] = "a"
, so increment bothi
andj
. - Since
s[1]
is "b" and doesn't match"ale"[1]
("l"), onlyi
is incremented. - Continue incrementing
i
until we find a match for each character of"ale"
. - When
j
reaches the end of"ale"
, we know it is a subsequence ofs
. - Update
ans
with"ale"
as it is currently the longest word found.
- Initialize two pointers,
-
Next, for the word
"apple"
:- Repeat the same
check
procedure. - The word
"apple"
is also found to be a subsequence withins
by matching "a", "p", "p", "l" and skipping the unused characters. - Since
"apple"
is longer than"ale"
, updateans
with"apple"
.
- Repeat the same
-
Then, check the word
"monkey"
:- It is found that not all characters can be matched; thus, it is not a subsequence of
s
. No need to updateans
.
- It is found that not all characters can be matched; thus, it is not a subsequence of
-
Finally, for the word
"plea"
:- The
check
function will confirm that"plea"
is a subsequence ofs
. - Since
"plea"
is the same length as"apple"
, but not lexicographically smaller, we do not updateans
.
- The
-
After checking all words,
ans
contains"apple"
, which is the longest word that can be formed by deleting some characters froms
.
The result from our example is "apple"
, as it is the longest word that can be created from s
by deleting some characters, and it also adheres to the lexicographical order in case of length ties (even though there were none in this case).
Solution Implementation
1class Solution:
2 def findLongestWord(self, s: str, dictionary: List[str]) -> str:
3 # Helper function to check if b is a subsequence of a
4 def is_subsequence(a, b):
5 m, n = len(a), len(b)
6 pos_a = pos_b = 0
7 # Traverse both strings and check if b is subsequence of a
8 while pos_a < m and pos_b < n:
9 if a[pos_a] == b[pos_b]:
10 pos_b += 1 # Move pointer of string b if characters match
11 pos_a += 1 # Always move pointer of string a
12 # Check if reached the end of string b, meaning b is a subsequence of a
13 return pos_b == n
14
15 # Initialize the answer to an empty string
16 longest_word = ''
17
18 # Iterate over each word in the given dictionary
19 for word in dictionary:
20 # Check if the word is a subsequence of s
21 # Update longest_word if word is longer or lexicographically smaller
22 if is_subsequence(s, word) and (len(longest_word) < len(word) or
23 (len(longest_word) == len(word) and longest_word > word)):
24 longest_word = word
25 # Return the longest word that is a subsequence of s and satisfies the condition
26 return longest_word
27
1class Solution {
2
3 // Function to find the longest word in the dictionary that can be formed by deleting
4 // some characters of the given string s.
5 public String findLongestWord(String s, List<String> dictionary) {
6 String longestWord = "";
7 for (String word : dictionary) {
8 // Check if current word can be formed by deleting some characters from s
9 if (isSubsequence(s, word)) {
10 // Update longestWord if current word is longer, or the same length but lexicographically smaller
11 if (longestWord.length() < word.length() ||
12 (longestWord.length() == word.length() && word.compareTo(longestWord) < 0)) {
13 longestWord = word;
14 }
15 }
16 }
17 return longestWord;
18 }
19
20 // Helper method to check if string a is a subsequence of string b
21 private boolean isSubsequence(String a, String b) {
22 int i = 0; // Pointer for string a
23 int j = 0; // Pointer for string b
24 int m = a.length();
25 int n = b.length();
26
27 while (i < m && j < n) {
28 if (a.charAt(i) == b.charAt(j)) {
29 // If current characters match, move pointer j to next position in string b
30 ++j;
31 }
32 // Always move pointer i to next position in string a
33 ++i;
34 }
35
36 // If we have traversed the entire string b, it means it is a subsequence of a
37 return j == n;
38 }
39}
40
1class Solution {
2public:
3 // Function to find the longest string in the dictionary that is a
4 // subsequence of s. If there are multiple, the smallest lexicographically
5 // will be returned.
6 string findLongestWord(string s, vector<string>& dictionary) {
7 string longestWord = ""; // Initialize the longest word to an empty string
8
9 // Iterate over each word in the dictionary
10 for (string& word : dictionary) {
11 // Check if the word is a subsequence of s
12 // and compare it with the current longest word based on length and lexicographical order
13 if (isSubsequence(s, word) &&
14 (longestWord.size() < word.size() ||
15 (longestWord.size() == word.size() && word < longestWord))) {
16 longestWord = word; // Update the longest word
17 }
18 }
19 return longestWord; // Return the longest word
20 }
21
22 // Helper function to check if string b is a subsequence of string a
23 bool isSubsequence(string& a, string& b) {
24 int aLength = a.size(), bLength = b.size(); // Length of the strings
25 int i = 0, j = 0; // Pointers for each string
26
27 while (i < aLength && j < bLength) {
28 // If the characters match, increment j to check the next character of b
29 if (a[i] == b[j]) ++j;
30 ++i; // Always increment i to move forward in string a
31 }
32 // String b is a subsequence of a if j has reached the end of b
33 return j == bLength;
34 }
35};
36
1function findLongestWord(s: string, dictionary: string[]): string {
2 // Sort the dictionary in descending order by word length.
3 // If two words have the same length, sort them lexicographically in ascending order.
4 dictionary.sort((word1, word2) => {
5 if (word1.length === word2.length) {
6 return word1.localeCompare(word2);
7 }
8 return word2.length - word1.length;
9 });
10
11 // Store the length of the string `s`.
12 const stringLength = s.length;
13
14 // Iterate over the sorted dictionary.
15 for (const targetWord of dictionary) {
16 // Store the length of the current target word.
17 const targetLength = targetWord.length;
18
19 // If the target word is longer than the string `s`, it cannot be formed.
20 if (targetLength > stringLength) {
21 continue;
22 }
23
24 // Initialize two pointers for comparing characters in `s` and the target word.
25 let stringPointer = 0;
26 let targetPointer = 0;
27
28 // Iterate over the characters in `s` and the target word.
29 while (stringPointer < stringLength && targetPointer < targetLength) {
30 // If the current characters match, move the target pointer to the next character.
31 if (s[stringPointer] === targetWord[targetPointer]) {
32 targetPointer++;
33 }
34 // Always move the string pointer to the next character.
35 stringPointer++;
36 }
37
38 // If all characters of the target word have been found in `s` in order,
39 // then the target word can be formed. Return it as the answer.
40 if (targetPointer === targetLength) {
41 return targetWord;
42 }
43 }
44
45 // If no word from the dictionary can be formed by `s`, return an empty string.
46 return '';
47}
48
Time and Space Complexity
The given Python code defines a function findLongestWord
that looks for the longest string in the dictionary
that can be formed by deleting some of the characters of the string s
. If there are more than one possible results, it returns the smallest in lexicographical order.
Time Complexity
Time Complexity: O(n*m + n*log(n))
Here n
is the size of dictionary
and m
is the length of the string s
.
- The function
check(a, b)
has a time complexity ofO(m)
, because in the worst case, it will check each character in strings
againstb
. - This check function is called for every word in the dictionary, resulting in
O(n*m)
. - Additionally, sorting the dictionary in lexicographic order is required to ensure we get the smallest word when lengths are equal. Sorting a list of strings takes
O(n*log(n)*k)
, wherek
is the average length of strings; however, since we're not sorting the dictionary, we're not including this in our complexity analysis.
Space Complexity
Space Complexity: O(1)
- No additional space is needed that grows with the input size. Only variables for iterating and comparison are used which occupy constant space.
- Thus, the space complexity is constant since the only extra space used is for pointer variables
i
andj
, and variableans
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!