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

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

https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/solution/524tong-guo-shan-chu-zi-mu-pi-pei-dao-zi-k1d2/

难度：中等

题目

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

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

提示：

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

示例

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

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

分析

如果dictionary是一个字符串，那个大家肯定都会比较了，无非是一个指针求子串的问题。 但是现在他是一个列表又该如何实现？其实只需要针对列表进行排序即可。 按照长度的逆序和字符串比较的升序完成列表排序，然后循环判断即可获得最终结果。 具体代码如下：

解题

Python:

class Solution:
    def findLongestWord(self, s: str, dictionary):
        for word in sorted(dictionary, key=lambda x: [-len(x), x]):
            p = 0
            for i in s:
                if word[p] == i: p += 1
                if p == len(word): return word
        return ''

Java:

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        dictionary.sort((o1, o2) -> o1.length() != o2.length() ?
                o2.length() - o1.length() : o1.compareTo(o2));
        for (String word : dictionary) {
            int p = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == word.charAt(p)) {
                    p++;
                }
                if (p == word.length()) return word;
            }
        }
        return "";
    }
}

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown