C++(3ms) sort + subsequence check


  • 0
    G

    A little long, but it is very easy to understand. We can just simply check when the string is likely to be the longest uncommon sequence because of the small scale of the data.

    int searchList[55];
    
    bool isShort(const string& str1,const string& str2){
    	if(str1.length() != str2.length()) return str1.length() > str2.length();
    	else return str1 < str2;
    }
    
    class Solution {
    public:
    	int findLUSlength(vector<string>& strs) {
    		memset(searchList,-1,sizeof(searchList));
    		sort(strs.begin(),strs.end(),isShort);
    		if(strs[1] != strs[0]) return strs[0].length();
    		searchList[0] = 0;
    		for(int i = 1,j = 1;i < strs.size();i++){
    			if(strs[i - 1] != strs[i]){
    				searchList[j++] = i;
    				if(i == strs.size() - 1
    					|| (i < strs.size() - 1 && strs[i + 1] != strs[i])){
    					int k = j - 2;
    					for(;k >= 0;k--){
    						if(isCommon(strs[i],strs[searchList[k]])) break;
    					}
    					if(k == -1) return strs[i].length();
    				}
    			}
    		}
    		return -1;
    	}
    private:
    	bool isCommon(const string& str1,const string& str2){
    		if(str1.length() == str2.length()) return str1 == str2;
    		for(int i = 0,j = 0;i < str1.length();i++){
    			for(;j < str2.length();j++){
    				if(str1[i] == str2[j]) break;
    			}
    			if(j == str2.length()) return false;
    			else j++;
    		}
    		return true;
    	}
    };
    

Log in to reply
 

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