Longest Word in Dictionary through Deleting | February Leetcoding Challenge 2021 | Day 22
logo
Manas Sinha
Developer | Designer

By Manas | 22 February 2021

February LeetCoding Challenge 2021

Day 22

Longest Word in Dictionary through Deleting

PROBLEM  STATEMENT:
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.
Example 1
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output: 
"apple"
Example 2
Input:
s = "abpcplea", d = ["a","b","c"]
Output: 
"a"
Note:
  • All the strings in the input will only contain lower-case letters.
  • The size of the dictionary won’t exceed 1,000.
  • The length of all the strings in the input won’t exceed 1,000.
 

Explanation

The brute force approach will be to find all the possible strings that the given string s can form and check that the string is present in the dictionary.The more optimal approach however will be to search backwards, i.e, if the words of the dictionary are present as the sub sequence of the string s and then return the longest word. To simplify this more we can sort the words of the dictionary by length/lexicographically and return the first word that is found as the sub sequence of the given string.
ALGORITHM:
  • Sort the words of the dictionary by length or in lexicographic order (if length is same).
  • Iterate over the words of the dictionary and check if it present as a sub sequence of the given string.
  • If such a word is found return it.
  • If no such word is found return empty string.
  • Time complexity : O(n*x*log(n)+n*m). n is the number of words in list d, x is average length of the words, and m is length of input string s.
  • Space complexity : O(logn). Sorting takes O(logn) space in average case
Alternatively, it can also be done without sorting by just checking all the words of list d and returning the string that satisfies the required length and lexicographic criteria.
  • Time complexity : O(n*m). n is the number of words in list d and m is length of input string s.
  • Space complexity : O(x). x is average length of the words. We are maintaing a max_str string.

code (with sorting)

C++

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        ios_base::sync_with_stdio(0),cin.tie(0);
        
        auto comp = [](string a,string b){
            if(a.length() == b.length())
                return a<b;
             return a.length()>b.length();
        };
        
        sort(d.begin(),d.end(),comp);
        
        for(string word : d){
            int idx = 0;
            
            for(auto c : s){
                if(c == word[idx]) idx++;
                if(idx == word.length()) return word;
                }
            }
       return "";
    }
};

PYTHON

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        
        d = sorted(d,key = lambda x: (-len(x),x))

        for word in d:
            idx = 0   
            for c in s:
                if(c == word[idx]):
                    idx += 1
                if(idx == len(word)):
                    return word
        return ""
        

code (WITHOUT SORTING)

C++

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        ios_base::sync_with_stdio(0),cin.tie(0);
        
        string res = "";
        for(string word : d){
            int idx = 0;
            
            for(auto c : s){
                if(c == word[idx]) idx++;
                if(idx == word.length()){
                    if(word.length() > res.length() || (word.length() == res.length() && word<res))
                        res = word;
                    break;
                    }
                }
            }
       return res;
    }
};

PYTHON

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        res = ''

        for word in d:
            idx = 0   
            for c in list(s):
                if(c == word[idx]):
                    idx += 1
                if(idx == len(word)):
                    if(len(word)>len(res) or len(word)==len(res) and word<res):
                        res = word
                    break
        return res
        

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply