13ms java two hashset solution with explaination


  • 0
    S

    after fooled by longest uncommon subsequence I this question becomes clear. If there is a duplicate, this word will definitely not be considered to be out candidate. So I maintained two Hash set, one save the words that occur only once and the other save the words occur more than once and then just simply look at whether there is a word in duplicate set has a subsequence of this word. If there is one, this word only occur once will also not be our candidate.

    public class Solution {
        public int findLUSlength(String[] strs) {
            HashSet<String> once = new HashSet<>();
            HashSet<String> more = new HashSet<>();
            for(String s : strs){
                if(once.contains(s)){
                    once.remove(s);
                    more.add(s);
                }else
                    once.add(s);
            }
            if(once.size() == 0) return -1;
            int max = -1;
            for(String s : once){
                boolean has = false;
                for(String dup : more){
                    if(has(dup, s)){
                        has = true;
                        break;
                    }
                }
                if(!has) max = Math.max(max, s.length());
            }
            return max;
        }
        private boolean has(String longer, String shorter){
            int index1 = 0, index2 = 0;
            while(index1 < longer.length() && index2 < shorter.length()){
                while(index1 < longer.length() && longer.charAt(index1) != shorter.charAt(index2)) index1++;
                if(index1 < longer.length() && index2 == shorter.length() - 1) return true;
                index1++;
                index2++;
            }
            return false;
        }
    }
    

Log in to reply
 

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