524. 通过删除字母匹配到字典里最长单词

骑猪看日落 2022-10-16 09:47 98阅读 0赞

> 给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
> 
> 如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
> 
>  
> 
> 示例 1：
> 
> 输入：s = "abpcplea", dictionary = \["ale","apple","monkey","plea"\]  
> 输出："apple"  
> 示例 2：
> 
> 输入：s = "abpcplea", dictionary = \["a","b","c"\]  
> 输出："a"

集合自定义比较器:

![20210529153336757.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        public String findLongestWord(String s, List<String> dictionary) {
            /**
            对集合进行按串长度进行排序
            然后遍历排好序的集合,然后进行判断(s是不是删掉之后可以组成当前串)
             */
            //对集合进行按串长度进行排序
            Collections.sort(dictionary,new Comparator<String>(){
                public int compare(String o1,String o2){
                    //让串长度顺序从大到小排序  "abce" ["abe","abc"] ->abc 所以还得o2.compareTo(o1)
                    if(o2.length()==o1.length()){
                        return o1.compareTo(o2);
                    }else{
                       return  o2.length()-o1.length();
                    }
                   
                }
            });
    
            //然后遍历排好序的集合,
    
            for(String str:dictionary){
               
                //然后进行判断(s是不是删掉之后可以组成当前串) ->双指针方法判断
                if(isSon(str,s)){
                    return str;
                }
            }
    
            return "";
        }
    
        //双指针方法判断 是否是子串
        public boolean isSon(String s1,String s2){
            int l=0,r=0;
            while(l<s1.length()&&r<s2.length()){
                if(s1.charAt(l)==s2.charAt(r)){
                    l++;
                    r++;
                }else{
                    r++;
                }
            }
            return l==s1.length();
        }
    }

[20210529153336757.png]: /images/20221014/9b137c83faa347c3a2da66c32268b06e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221014/070ab262bab24c91a5e73cf0c0a64e8b.png