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

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

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

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 仅由小写英文字母组成

今日每日一题

先按照题面说明来一版直接计算比较的

public class Solution{
    public String findLongestWord(String s, List<String> dictionary) {
        String str = "";
        int deleteCount;
        for (String s1 : dictionary) {
            deleteCount = deleteCount(s,s1);
            if(deleteCount >=0){
                if (s1.length() > str.length()){
                    str = s1;
                }else if (s1.length() == str.length()){
                    str = dictionaryCompare(s1,str)>0? s1:str;
                }
            }
        }
        return str;
    }


    /**
     * 从字符串  asdfgh 删除字母变成  sf
     * @param a
     * @param b
     * @return
     */
    public int deleteCount(String a ,String b){
        int count = 0;
        //i表示a上的指针，j表示b上的指针
        int i = 0,j = 0;
        while (i< a.length() && j < b.length()){
            if (a.charAt(i)==b.charAt(j)){
                j++;
                count++;
                if (count == b.length()){
                    break;
                }
            }
            i++;
        }
        if (count == b.length()){
            return a.length()-count;
        }
        return Integer.MIN_VALUE;
    }


    public int dictionaryCompare(String a, String b){
        int i = 0;
        while (i < a.length()){
            if (a.charAt(i) == b.charAt(i)){
                i++;
            }else{
                if (a.charAt(i) > b.charAt(i)){
                    return -1;
                }
                return 1;
            }
        }
        return 0;
    }
}

deleteCount函数计算从一个字符串中能否通过删除字母得到另一个字符串，如果可以则返回需要删除的字符个数，不能则返回一个负数。dictionaryCompare用来比较两个字符串的字典排序，逐个字符进行对比，相等则返回0，不等则根据比较情况返回1或者-1。

题面要求，找出字典里的最长字符串，可以试试先讲字典数组排序，修改主函数为如下

public String findLongestWord(String s, List<String> dictionary) {
    String str = "";
    int deleteCount;
    dictionary.sort(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.length()-o1.length();
        }
    });
    for (String s1 : dictionary) {
        deleteCount = deleteCount(s,s1);
        if(deleteCount >=0){
            if (str.length()==0){
                str = s1;
            }else if (s1.length() == str.length()){
                str = dictionaryCompare(s1,str)>0? s1:str;
            }else{
                break;
            }
        }
    }
    return str;
}