最长特殊序列 II

妖狐艹你老母 2022-01-10 05:47 266阅读 0赞

[最长特殊序列 II][II]

class Solution {
        boolean containsSub(String s,String p){
            int i,j;
            for(i=0,j=0;i<p.length()&&j<s.length();j++)
                if(s.charAt(j)==p.charAt(i))
                    i++;
            if(i>=p.length())return true;
            return false;
        }
        void removeStr(String p,LinkedList<String>list){
            if(list.contains(p)){
                String s="";
                for(int i=0;i<list.size();i++){
                    s=list.get(i);
                    if(s.length()<p.length()&&containsSub(p,s)){
                        removeStr(s,list);
                    }
                }
                list.remove(p);
            }
        }
        public int findLUSlength(String[] strs) {
            int n=strs.length;
            HashMap<String,Integer>map=new HashMap<>();
            for(String s:strs)
                if(map.containsKey(s))
                    map.replace(s, map.get(s)+1);
                else
                    map.put(s, 1);
            LinkedList<String>list=new LinkedList<>();
            for(String s:map.keySet())    
                list.addFirst(s);
            list.sort(new Comparator<String>(){
    
                @Override
                public int compare(String o1, String o2) {
                    // TODO Auto-generated method stub
                    return o2.length()-o1.length();
                }
                
            });
            int last=list.size(),i=0;
            while(i<list.size()){
                if(map.get(list.get(i))>1)
                    removeStr(list.get(i),list);
                else
                    i++;
                if(last==list.size())break;
                else last=list.size();
            }    
            if(list.size()==0)return -1;
            return list.getFirst().length();
        }
    }

坑：判断包含关系和递归删除

转载于:https://www.cnblogs.com/yuelien/p/10553778.html

[II]: https://leetcode-cn.com/problems/longest-uncommon-subsequence-ii/