C++: Sorting and Hash Set


  • 0
    E

    The idea is to sort the list of strings by their length. If different strings have the same length, we sort them by lexicographical order. We can use the sort function included in the STL, providing a custom predicate as a lambda function. Sorting takes O(n * log n) time complexity, where n is the number of words in the list.
    Once sorted we scan the list and insert the current word in a hash set if the same word without the last character is already present in this set. This will result in O(n) time complexity, and O(n) space complexity.
    The overall solution takes O(n * log n) time complexity and O(n) space complexity.
    Here is the code implementation:

    class Solution {
    public:
       string longestWord(vector<string>& words) {
        
        string longest;
        unordered_set<string> h;
        
        h.insert("");
        
        std::sort(words.begin(),
                  words.end(),
                 [](string str1, string str2) { return str1.size() < str2.size() ||
                                                       (str1.size() == str2.size() && str1 < str2); });
        
        for (const auto& word : words)
        {
            if (h.find(word.substr(0, word.size() - 1)) != h.end())
            {
                if (word.size() > longest.size())
                {
                    longest = word;
                }
                
                h.insert(word);
            }
        }
        
        return longest;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.