java solution using TreeMap (17 ms)


  • 0

    My idea for this problem:
    for example, we have following input: "aabbcc", "aabbcc", "bcc", "bc"

    1. using TreeMap<Integer,List<String>> (key is the length of string):
      deal with the input into: 6 : aabbcc , aabbcc
      3: bcc
      2: bc
    2. sort all of the values (List<String>) using CompareTo
    3. find the candidate which can be the final result from every list:
      word indexed i can be a candidate if it is not equals to the two words indexed i-1 and i+1;
    4. make sure if this candidate is the final result:
      compare this candidate to all of the words which is longer than it, if it is not a subsequence to any longer words, this word is the final result.

    My solution is quit complex, if you have some better idea, please post your solution. Thanks~

    public class Solution {
        public int findLUSlength(String[] strs) {
            if(strs == null || strs.length == 0) {
                return -1;
            }
            TreeMap<Integer,List<String>> map = new TreeMap<Integer,List<String>>();
            for(int i = 0; i < strs.length; i++) {
                if(map.containsKey(strs[i].length())) {
                    map.get(strs[i].length()).add(strs[i]);
                }else {
                    List<String> list = new ArrayList<String>();
                    list.add(strs[i]);
                    map.put(strs[i].length(), list);
                }
            }
            List<Integer> lenlist = new ArrayList<Integer>();
            for(Map.Entry<Integer,List<String>> entry : map.entrySet()) {
                List<String> list = entry.getValue();
                Collections.sort(list, new Comparator<String>() {
                    public int compare(String s1, String s2) {
                        if(s1.compareTo(s2) < 0) {
                            return -1;
                        }else {
                            return 1;
                        }
                    }
                    });
                lenlist.add(entry.getKey());
            }
            return helper(map, lenlist);
        }
        
        protected int helper(TreeMap<Integer,List<String>> map, List<Integer> lenlist) {
            for(int i = lenlist.size() - 1; i >= 0; i--) {
                List<String> wordlist = map.get(lenlist.get(i));
                for(int j = 0; j < wordlist.size(); j++) {
                    if(iscandidate(j, wordlist)) {
                        if(i == lenlist.size()-1) {
                            return lenlist.get(i);
                        }else {
                            int p = i+1;
                            List<String> templist = new ArrayList<String>();
                            while(p < lenlist.size()) {
                                templist.addAll(map.get(lenlist.get(p)));
                                p++;
                            }
                            boolean tag = false;
                            for(String s : templist) {
                                if(issubstr(s, wordlist.get(j))) {
                                    tag = true;
                                    break;
                                }
                            }
                            if(!tag) {
                                return wordlist.get(j).length();
                            }
                        }
                    }
                }
            }
            return -1;
        }
        
        protected boolean iscandidate(int index, List<String> wordlist) {
            if(wordlist.size() == 1) {
                return true;
            }
            if(index == 0) {
                return !wordlist.get(0).equals(wordlist.get(1));
            }else if(index == wordlist.size() - 1) {
                return !wordlist.get(index-1).equals(wordlist.get(index));
            }else {
                return !wordlist.get(index-1).equals(wordlist.get(index)) && !wordlist.get(index).equals(wordlist.get(index+1));
            }
        }
        
        protected boolean issubstr(String s1, String s2) {
            int p = 0;
            for(int i = 0; i < s1.length(); i++) {
                if(p == s2.length()) {
                    return true;
                }
                if(s1.charAt(i) == s2.charAt(p)) {
                    p++;
                }
            }
            return p == s2.length();
        }
    }

Log in to reply
 

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