【Leetcode刷题记录】524. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例1：
输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”

解题思路其实比较清晰，就是首先对给的待匹配字典的里字符串进行排序，规则就是长的字符串在前，长度一样的按照字典序进行排序，然后就是遍历字典中字符串，返回满足要求的第一个串，个人在实现进行比对判断的时候用了数组空间存s串中的字符的下标然后再遍历比对，后看别人题解，其实此处比多判断用两个指针分别指向s和带判断dictionary[i]就行

未使用双指针

 public static class tComparator implements Comparator{
	        public int compare(String a,String b){
	            if(a.length()!=b.length()) return b.length() - a.length();
	            else{
	                for(int i=0;i dictionary) {
	        
	        
	        List> sites = new ArrayList<>();
	        for(int i=0;i<26;i++){//还是先初始化一下吧
	            sites.add(i,new ArrayList<>());
	        }
	        for(int i=0;i n = sites.get(s.charAt(i)-'a');
	            sites.get(s.charAt(i)-'a').add(i);
	        dictionary.sort(new tComparator());
	        for(int i=0;i path = new ArrayList<>();
	            int j = 0;
	            for(;j=0&&sites.get(k).get(ks)>path.get(j-1)){
	                        break;
	                    }
	                    ks++;
	               
	                    
	                }
	           
	                if(ks>sites.get(k).size()-1) break; //如果满足，退出的时候应该是正好需要的ks的位置        
	                path.add(sites.get(k).get(ks));
	
	            }
	            if(j>=sd.length()){//完成遍历退出，则应该是符合的
	                return sd;
	            }

	        }
	        return "";
	    }

使用双指针

public String findLongestWord(String s, List dictionary) {
        
        dictionary.sort(new tComparator());
       //排好序之后，查找的时候两个指针遍历控制就好了，不用再用额外的数组存信息找，其实实际上是一个意思
       for(int k=0;ks.length()) continue;
           int i=0;//遍历字符串s
           int j=0;//遍历字符串sd
           while(i=sd.length()) return sd; //表示找到满足要求的结果
       }
        return "";
    }