12ms Java two HashSet solution


  • 0
    public class Solution {
        // Test if target is a subsequence of origin
        private boolean isSubsequence(String origin, String target) {
            if(target.length() > origin.length()) {
                return false;
            } else if(target.length() == origin.length()) {
                return target.equals(origin);
            } else {
                int startI = 0;
                for(int i=0; i<target.length(); i++) {
                    int foundI = origin.indexOf(target.charAt(i), startI);
                    if(foundI==-1)
                        return false;
                    startI = foundI + 1;
                }
                return true;
            }
        }
        
        public int findLUSlength(String[] strs) {
            Set<String> candidateSet = new HashSet<>();
            Set<String> impossibleSet = new HashSet<>();
            for(String s : strs) {
                if(!impossibleSet.contains(s)) {
                    if(candidateSet.contains(s)) {
                        candidateSet.remove(s);
                        impossibleSet.add(s);
                    } else {
                        boolean isGood = true;
                        for(String impS : impossibleSet) {
                            if(isSubsequence(impS, s)) {
                                isGood = false;
                                break;
                            }
                        }
                        if(!isGood) {
                            candidateSet.remove(s);
                            impossibleSet.add(s);
                        } else {
                            candidateSet.add(s);
                        }
                    }
                }
            }
            int res = -1;
            for(String s : candidateSet)
                res = Math.max(res, s.length());
            return res;
        }
    }

Log in to reply
 

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