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

import java.util.List;

class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String result = "";
for (String word : dictionary) {
// 只有能作为 s 的子序列，才可能通过删除字母得到
if (isSubsequence(word, s)) {
// 更长的优先；长度相同取字典序更小的
if (word.length() > result.length()
|| (word.length() == result.length() && word.compareTo(result) < 0)) {
result = word;
}
}
}
return result;
}

// 判断 word 是否为 s 的子序列
private boolean isSubsequence(String word, String s) {
int i = 0, j = 0;
while (i < word.length() && j < s.length()) {
if (word.charAt(i) == s.charAt(j)) {
i++;
}
j++;
}
return i == word.length();
}
}

思路

题目本质是：在字典中找出所有是 s 的子序列的单词，在这些单词中返回长度最大的；若长度相同，返回字典序最小的。

排序优化版本

也可以先按“长度降序、字典序升序”排序，返回第一个子序列匹配的单词，逻辑更直观：

import java.util.List;

class Solution {
public String findLongestWord(String s, List<String> dictionary) {
dictionary.sort((a, b) ->
a.length() != b.length() ? b.length() – a.length() : a.compareTo(b));

for (String word : dictionary) {
if (isSubsequence(word, s)) {
return word;
}
}
return "";
}

private boolean isSubsequence(String word, String s) {
int i = 0, j = 0;
while (i < word.length() && j < s.length()) {
if (word.charAt(i) == s.charAt(j)) {
i++;
}
j++;
}
return i == word.length();
}
}

关键点

· 子序列判定：只需保持两个指针单向扫描，O(|word| + |s|) 时间。
· 字典序比较：String.compareTo 返回值小于 0 表示前者字典序更小。
· 相同长度：必须比较字典序，不能随便返回一个。
· 排序不能简单地只按长度降序，因为同长度下字典序要求最小，所以要按 (长度降序, 字典序升序) 复合排序。

复杂度

· 时间复杂度：O(d * L)，其中 d 为字典大小，L = |s| + 最长单词长度；排序版本额外有 O(d log d) 的排序开销。
· 空间复杂度：O(1)（不计输入），排序版本为 O(log d) 栈空间。