C++ Solution using DFS and HashTable


  • 0
    Y
    class Solution {
    public:
        int findLUSlength(vector<string>& strs) {
            int ans = -1;
            if(strs.size() == 0)
                return ans;
            unordered_set<string> vis, allst, vec_s;
            unordered_set<string>::iterator it;
            unordered_map<string,int> dict;
            if(init(dict,strs,vec_s) == false)
                return ans;
            for(int i = 0; i < strs.size(); ++ i){
                if(vec_s.find(strs[i]) == vec_s.end()){
                    calcAllset(allst, strs[i]);
                }
            }
            
            for(it = vec_s.begin(); it != vec_s.end(); ++ it){
                string tmp = "", s = *it;
                vis.clear();
                dfs(vis, allst, tmp, s, 0, ans, vec_s);
            }
            
            return ans;
        }
    private:
        bool check(string &s, unordered_set<string> &vec_s, string &v){
            unordered_set<string>::iterator it;
            for(it = vec_s.begin(); it != vec_s.end(); ++ it){
                string u = *it;
                if(u != s){
                    int i = 0, j = 0;
                    while(i < u.size() && j < v.size()){
                        if(u[i] == v[j])
                            ++ j;
                        ++ i;
                    }
                    if(j >= v.size())
                        return false;
                }
            }
            return true;
        }
    
        void dfs(unordered_set<string> &vis, unordered_set<string> &allst, string &tmp, string &s, int sta, int &ans, unordered_set<string> &vec_s){
            for(int i = sta; i < s.size(); ++ i){
                string newtmp = tmp + s[i];
                if(allst.find(newtmp) == allst.end() && check(s, vec_s, newtmp)){
                    ans = max(ans, (int)newtmp.size());
                }
                if(vis.find(newtmp) == vis.end()){
                    vis.insert(newtmp);
                    dfs(vis, allst, newtmp, s, i + 1, ans, vec_s);
                }
            }
        }
    
        void dfsAllst(unordered_set<string> &allst, string &s, string &strs, int sta){
            for(int i = sta; i < strs.size(); ++ i){
                string tmp = s + strs[i];
                allst.insert(tmp);
                dfsAllst(allst, tmp, strs, i + 1);
            }
        }
    
        void calcAllset(unordered_set<string> &allst, string &strs){
            for(int i = 0; i < strs.size(); ++ i){
                string s = "";
                s.append(1, strs[i]);
                allst.insert(s);
                dfsAllst(allst, s, strs, i + 1);
            }
        }
    
        bool init(unordered_map<string,int> &dict, vector<string>& strs, unordered_set<string> &vec_s){
            dict.clear();
            for(int i = 0; i < strs.size(); ++ i)
                ++ dict[strs[i]];
            bool hasCandidate = false;
            unordered_map<string,int>::iterator it;
            string tmp;
            for(it = dict.begin(); it != dict.end(); ++ it){
                if(it->second == 1){
                    tmp = it->first;
                    vec_s.insert(tmp);
                    hasCandidate = true;
                }
            }
            return hasCandidate;
        }
    };
    

Log in to reply
 

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