Java 10ms, no extra space


  • 0

    No extra space if we don't consider about space used in the sorting process (can use heapsort if necessary).

    public class Solution {
        public int findLUSlength(String[] strs) {
            if(strs==null || strs.length==0) return -1;
            Arrays.sort(strs, new Comparator<String>(){//default comparator is based on alphabet order but not length
                @Override
                    public int compare(String s1, String s2){
                        return s1.length()-s2.length();
                    }
                });
            for(int i=strs.length-1; i>=0; i--){
                String str=strs[i];
                boolean isSubstring=false;
                for(int j=strs.length-1; j>=0 && strs[j].length()>=str.length(); j--){//must comapre with other same length string
                    if(j==i) continue; //can't compare to itself
                    if(isSubstring(str, strs[j])){
                        isSubstring=true;
                        break;
                    }
                }
                if(!isSubstring) return str.length();
            }
            return -1;
        }
        
        private boolean isSubstring(String s1, String s2){
            int i=0, j=0, len1=s1.length(), len2=s2.length();
            while(i<len1 && j<len2 && len2-j>=len1-i){
                if(s1.charAt(i)==s2.charAt(j)){
                    i++;
                    j++;
                }else j++;
            }
            return i==len1;
        }    
    }
    

Log in to reply
 

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