C++ 6ms sort + hashset


  • 0
    B

    I first sort all strings by length, with the longest string in the beginning. Therefore we start from the longest string, and any uncommon string found will be the longest uncommon subsequence.

    In the main loop, each step deals with unvisited strings of the same length (level).

    I first create a set unique to store all unique string of the current length (level). This step allows us to exit the function early if an uncommon subsequence if found, without searching through all strings in vector strs.

    I then check each unique string of length level, to see if they're in fact uncommon by comparing against all visited (which will be of greater or equal length) strings stored in set all. We return level, which is the string length of the current loop step, if an uncommon string is found.

    class Solution {
    private:
        // checks if string u is a subsequence to any strings in set all
        bool isuncommon(string u, set<string>& all) {
            for (string s:all) {
                if (u!=s) { // u is always in the set all, we do not compare u with itself
                    string temp=u;
                    for (char c:s) {
                        if (temp.front()==c) temp.erase(temp.begin());
                    }
                    if (temp.size()==0) return false;
                }
            }
            return true;
        }
    public:
        int findLUSlength(vector<string>& strs) {
            // sort strs vector by string length
            sort(strs.begin(),strs.end(),[](string a, string b){return a.size()>b.size();});
            
            set<string> all; // stores all visited strings
            
            while (!strs.empty()) {
                int level=strs.front().size();
                set<string> unique; // stores potential unique strings with the current length
                
                // compares all potential unique strings with the same length
                while (!strs.empty() && strs.front().size()==level) {
                    string s=strs.front();
                    if (unique.find(s)==unique.end() && all.find(s)==all.end()) unique.insert(s);
                    else unique.erase(s);
                    all.insert(s);
                    strs.erase(strs.begin());
                }
                
                // compares potential unqiue strings with all visisted strings
                for (string u:unique) if (isuncommon(u,all)) return level;
            }
            return -1;
        }
    };
    

Log in to reply
 

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