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.
Input: s = "abpcplea", d = ["ale","apple","monkey","plea"] Output: "apple"
Input: s = "abpcplea", d = ["a","b","c"] Output: "a"
The idea behind this approach is as follows. We create a list of all the possible strings that can be formed by deleting one or more characters from the given string . In order to do so, we make use of a recursive function
generate(s, str, i, l) which creates a string by adding and by removing the current character() from the string to the string formed till the index . Thus, it adds the character to and calls itself as
generate(s, str + s.charAt(i), i + 1, l). It also omits the character to and calls itself as
generate(s, str, i + 1, l).
Thus, at the end the list contains all the required strings that can be formed using . Then, we look for the strings formed in into the dictionary available to see if a match is available. Further, in case of a match, we check for the length of the matched string to maximize the length and we also take care to consider the lexicographically smallest string in case of length match as well.\n\n
Time complexity : .
generate calls itself times. Here, refers to the length of string .
Space complexity : . List contains strings.\n
Instead of using recursive
generate to create the list of possible strings that can be formed using by performing delete operations, we can also do the same process iteratively. To do so, we use the concept of binary number generation.
We can treat the given string along with a binary represenation corresponding to the indices of . The rule is that the character at the position has to be added to the newly formed string only if there is a boolean 1 at the corresponding index in the binary representation of a number currently considered.\n
We know a total of such binary numbers are possible if there are positions to be filled( also corresponds to the number of characters in ). Thus, we consider all the numbers from to in their binary representation in a serial order and generate all the strings possible using the above rule.\n
The figure below shows an example of the strings generated for the given string :"sea".\n
A problem with this method is that the maximum length of the string can be 32 only, since we make use of an integer and perform the shift operations on it to generate the binary numbers.\n\n
Time complexity : . strings are generated.\n
Space complexity : . List contains strings.\n
The matching condition in the given problem requires that we need to consider the matching string in the dictionary with the longest length and in case of same length, the string which is smallest lexicographically. To ease the searching process, we can sort the given dictionary\'s strings based on the same criteria, such that the more favorable string appears earlier in the sorted dictionary.\n
Now, instead of performing the deletions in , we can directly check if any of the words given in the dictionary(say ) is a subsequence of the given string , starting from the beginning of the dictionary. This is because, if is a subsequence of , we can obtain by performing delete operations on .\n
If is a subsequence of every character of will be present in . The following figure shows the way the subsequence check is done for one example:\n
As soon as we find any such , we can stop the search immediately since we\'ve already processed to our advantage.\n\n
Time complexity : . Here refers to the number of strings in list and refers to average string length. Sorting takes and
isSubsequence takes to check whether a string is a subsequence of another string or not.
Space complexity : . Sorting takes space in average case.\n
Since sorting the dictionary could lead to a huge amount of extra effort, we can skip the sorting and directly look for the strings in the unsorted dictionary such that is a subsequence in . If such a string is found, we compare it with the other matching strings found till now based on the required length and lexicographic criteria. Thus, after considering every string in , we can obtain the required result.\n\n
Time complexity : . One iteration over all strings is required. Here refers to the number of strings in list and refers to average string length.\n
Space complexity : . variable is used.\n
Analysis written by: @vinod23\n