share my o(n) solution


  • 0
    B
    class Solution {
    public:
        bool isSubSeq(string &s1, string &s2)
        {
            int i = 0, j;
            for (j = 0; j<s2.size() ; j++)
            {
                while (i<s1.size() && s1[i] != s2[j])
                {
                    i++;
                }
                if(i>=s1.size()) break;
                i++;
            }
            return j == s2.size();
        }
        int findLUSlength(vector<string>& strs) {
            map<int, unordered_set<string>> map;
            unordered_set<string> duplicated;
            for (auto x : strs)
            {
                if (map[x.size()].find(x) != map[x.size()].end())
                    duplicated.insert(x);
                else
                    map[x.size()].insert(x);
            }
            for (auto it = map.rbegin(); it != map.rend(); it++)
            {
                for (auto s : it->second)
                {
                    if (duplicated.find(s) != duplicated.end()) continue;
                    bool isSub = false;
                    for (auto it2 = map.rbegin(); it2 != it; it2++)
                    {
                        for (auto s2 : it2->second)
                        {
                            if (isSubSeq(s2, s))
                            {
                                isSub = true;
                                break;
                            }
                        }
                        if (isSub) break;
                    }
                    if (!isSub) return s.size();
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

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