当前位置：首页 > article >正文

24/12/24 力扣每日一题 # LeetCode 524. 通过删除字母匹配到字典里最长单词全网最详细解释

article 2024/12/25 22:51:43

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

难度：中等
相关标签：字符串、双指针、排序
相关企业：暂无

题目描述

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

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

示例 1

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
解释："apple" 可以通过删除 "abpcplea" 中的某些字符得到。

示例 2

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

提示

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

解题思路

为了找到 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到，我们可以采用以下步骤：

排序字典：
- 首先，我们需要将 dictionary 按照特定的规则进行排序：
  - 主排序关键字：字符串长度，降序。
  - 次排序关键字：字符串本身，字母序升序。
- 这样可以确保我们首先检查最长的字符串，如果有多个长度相同的字符串，则按字母序最小的优先。
检查子序列：
- 对于排序后的每个单词，我们需要检查它是否是字符串 s 的子序列。
- 使用双指针法，遍历 s 和 dictionary 中的单词，判断单词是否可以通过删除 s 中的某些字符得到。
返回结果：
- 一旦找到第一个满足条件的单词，即为所需的最长单词，直接返回。
- 如果遍历完所有单词都没有找到，返回空字符串。

代码实现

以下是根据上述思路实现的 Python 代码：

from typing import List

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        # 按长度降序，字母序升序排序
        dictionary.sort(key=lambda x: (-len(x), x))
        
        for word in dictionary:
            if self.is_subsequence(s, word):
                return word
        return ""
    
    def is_subsequence(self, s: str, word: str) -> bool:
        """
        检查 word 是否是 s 的子序列。
        使用双指针法，遍历 s 和 word。
        """
        a, b = 0, 0
        while a < len(s) and b < len(word):
            if s[a] == word[b]:
                b += 1
            a += 1
        return b == len(word)

代码详解

排序字典：
```
dictionary.sort(key=lambda x: (-len(x), x))
```
- 使用 lambda 函数作为排序关键字，返回一个元组 (-len(x), x)：
  - -len(x)：确保字符串按长度降序排序。
  - x：在长度相同的情况下，按字母序升序排序。
遍历字典并检查子序列：
```
for word in dictionary:
    if self.is_subsequence(s, word):
        return word
return ""
```
- 遍历排序后的 dictionary，对于每个单词，调用 is_subsequence 方法检查是否为 s 的子序列。
- 一旦找到符合条件的单词，立即返回该单词。
- 如果没有找到，返回空字符串。
子序列检查函数：
```
def is_subsequence(self, s: str, word: str) -> bool:
    a, b = 0, 0
    while a < len(s) and b < len(word):
        if s[a] == word[b]:
            b += 1
        a += 1
    return b == len(word)
```
- 使用双指针 a 和 b 分别遍历 s 和 word。
- 当 s[a] 和 word[b] 相等时，移动 b 指针，表示找到匹配的字符。
- 无论是否匹配，都移动 a 指针，继续遍历 s。
- 最后，检查 b 是否等于 word 的长度，若相等，则说明 word 是 s 的子序列。

示例运行

示例 1

s = "abpcplea"
dictionary = ["ale","apple","monkey","plea"]
solution = Solution()
print(solution.findLongestWord(s, dictionary))  # 输出: "apple"

解释：

排序后的 dictionary：["monkey", "apple", "plea", "ale"]
检查 "monkey"：不是 s 的子序列。
检查 "apple"：是 s 的子序列，返回 "apple"。

示例 2

s = "abpcplea"
dictionary = ["a","b","c"]
solution = Solution()
print(solution.findLongestWord(s, dictionary))  # 输出: "a"

解释：

排序后的 dictionary：["a", "b", "c"]
检查 "a"：是 s 的子序列，返回 "a"。

时间复杂度分析

排序：
- 对 dictionary 进行排序，时间复杂度为 O(n log n)，其中 n 是 dictionary 的长度。
子序列检查：
- 对于每个单词，最坏情况下需要遍历整个字符串 s，时间复杂度为 O(m)，其中 m 是 s 的长度。
- 在最坏情况下，需要检查所有单词，因此子序列检查的总时间复杂度为 O(n * m)。
总体时间复杂度：
- O(n log n + n * m)，其中 n 是 dictionary 的长度，m 是 s 的长度。