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

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

题目描述

给你一个字符串 s 和一个字符串数组 dictionary ,找出并返回 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] 仅由小写英文字母组成

题目解析

首先满足要求的只有一个值,根据规则要求:
1、字典中满足要求的最长字符串。
2、如果1中不满足,字符串相等的情况,则按字符串比较返回小的。
对字符串按这个规则排序,然后逐个匹配,遇到第一个满足要求的就是结果字符串。

s和dictionary[i]的匹配规则有严格的从左到右的顺序,所以用双指针法。
s[i]和dictionary[j][k]第一个字符开始比较,相等则i、k加1,不相等则i加1,直到k匹配完最后一个字符则满足要求,否则不满足要求。

代码实现

public String findLongestWord(String s, List<String> dictionary) {

        Collections.sort(dictionary, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() != o2.length()) return o2.length() - o1.length();
                return o1.compareTo(o2);
            }
        });
        int n = s.length();
        char[] cs = s.toCharArray();
        int length = dictionary.size();
        for (int i = 0; i < length; i++) {
            int dlength = dictionary.get(i).length();
            int j = 0,k = 0;
            while (j < n && k < dlength) {
                if (cs[j] == dictionary.get(i).charAt(k)) {
                    k++;
                }
                j++;

            }
            if (k == dlength) {
                return dictionary.get(i);
            }
        }
        return "";
    }

性能分析

排序复杂度mlogm,双指针复杂度为nm,m是指dictionary长度,n是指s的长度。所以总的时间复杂度为O(mlogm + nm)。

有不足之处多多指教
公众号:“计算机基础爱好者”
关注公众号回复“leetcode”,有leet-java.pdf书籍

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


下一篇:LeetCode524. 通过删除字母匹配到字典里最长单词