深圳app开发公司鑫酷_织梦模板修改教程_设计公司排名_app推广怎么联系一手代理

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 中的某些字符得到，我们可以采用以下步骤：

1. 排序字典：

   • 首先，我们需要将 dictionary 按照特定的规则进行排序：
     • 主排序关键字：字符串长度，降序。
     • 次排序关键字：字符串本身，字母序升序。
   • 这样可以确保我们首先检查最长的字符串，如果有多个长度相同的字符串，则按字母序最小的优先。

2. 检查子序列：

   • 对于排序后的每个单词，我们需要检查它是否是字符串 s 的子序列。
   • 使用双指针法，遍历 s 和 dictionary 中的单词，判断单词是否可以通过删除 s 中的某些字符得到。

3. 返回结果：

   • 一旦找到第一个满足条件的单词，即为所需的最长单词，直接返回。
   • 如果遍历完所有单词都没有找到，返回空字符串。

代码实现

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

from typing import Listclass 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 wordreturn ""def is_subsequence(self, s: str, word: str) -> bool:"""检查 word 是否是 s 的子序列。使用双指针法，遍历 s 和 word。"""a, b = 0, 0while a < len(s) and b < len(word):if s[a] == word[b]:b += 1a += 1return b == len(word)

代码详解

1. 排序字典：

   dictionary.sort(key=lambda x: (-len(x), x))
   

   • 使用 lambda 函数作为排序关键字，返回一个元组 (-len(x), x)：
     • -len(x)：确保字符串按长度降序排序。
     • x：在长度相同的情况下，按字母序升序排序。

2. 遍历字典并检查子序列：

   for word in dictionary:if self.is_subsequence(s, word):return word
   return ""
   

   • 遍历排序后的 dictionary，对于每个单词，调用 is_subsequence 方法检查是否为 s 的子序列。
   • 一旦找到符合条件的单词，立即返回该单词。
   • 如果没有找到，返回空字符串。

3. 子序列检查函数：

   def is_subsequence(self, s: str, word: str) -> bool:a, b = 0, 0while a < len(s) and b < len(word):if s[a] == word[b]:b += 1a += 1return 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 的长度。

空间复杂度分析

• 排序操作通常需要额外的空间，但在 Python 中，sort() 方法是就地排序，空间复杂度为 O(1)。
• 其他辅助空间主要来自于函数调用栈和变量，空间复杂度为 O(1)。
• 总体空间复杂度：O(1)

总结

通过对字典进行合适的排序，并利用双指针法高效地检查子序列关系，我们能够在合理的时间内找到满足条件的最长单词。这个方法不仅直观，而且性能良好，适用于大多数情况下的字符串处理问题。

希望这篇博客能够帮助你更好地理解 LeetCode 第 524 题及其解决方案。如果你有任何疑问或更好的解决方法，欢迎在评论区交流！