Medium

题目描述

给你一个字符串 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] 仅由小写英文字母组成

解题思路

这是一道典型的子序列匹配问题，核心是判断字典中的每个单词是否是字符串 s 的子序列。

解题思路：

  1. 子序列判断：使用双指针技术判断一个字符串是否是另一个字符串的子序列。对于字典中的每个单词，用一个指针遍历该单词，另一个指针遍历字符串 s，当字符匹配时两个指针都前进，否则只有 s 的指针前进。

  2. 结果选择：在所有能匹配的单词中，选择长度最长的。如果长度相同，选择字典序最小的。

  3. 优化策略：

    • 方法一：先按长度降序、字典序升序排序，找到第一个匹配的单词即为答案
    • 方法二：遍历所有单词，维护当前最优答案

推荐解法： 使用排序优化的方法，可以在找到第一个匹配的单词时立即返回，避免不必要的比较。

时间复杂度主要由排序和子序列匹配两部分组成，空间复杂度为常数级别。

代码实现

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        // 按长度降序，字典序升序排序
        sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b) {
            return a.length() != b.length() ? a.length() > b.length() : a < b;
        });
        
        // 检查第一个匹配的单词
        for (const string& word : dictionary) {
            if (isSubsequence(word, s)) {
                return word;
            }
        }
        return "";
    }
    
private:
    bool isSubsequence(const string& word, const string& s) {
        int i = 0, j = 0;
        while (i < word.length() && j < s.length()) {
            if (word[i] == s[j]) {
                i++;
            }
            j++;
        }
        return i == word.length();
    }
};

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.isSubsequence(word, s):
                return word
        return ""
    
    def isSubsequence(self, word: str, s: str) -> bool:
        i = j = 0
        while i < len(word) and j < len(s):
            if word[i] == s[j]:
                i += 1
            j += 1
        return i == len(word)

public class Solution {
    public string FindLongestWord(string s, IList<string> dictionary) {
        // 按长度降序，字典序升序排序
        var sortedDict = dictionary.OrderByDescending(w => w.Length)
                                  .ThenBy(w => w)
                                  .ToList();
        
        // 检查第一个匹配的单词
        foreach (string word in sortedDict) {
            if (IsSubsequence(word, s)) {
                return word;
            }
        }
        return "";
    }
    
    private bool IsSubsequence(string word, string s) {
        int i = 0, j = 0;
        while (i < word.Length && j < s.Length) {
            if (word[i] == s[j]) {
                i++;
            }
            j++;
        }
        return i == word.Length;
    }
}

var findLongestWord = function(s, dictionary) {
    function isSubsequence(word, str) {
        let i = 0, j = 0;
        while (i < word.length && j < str.length) {
            if (word[i] === str[j]) {
                i++;
            }
            j++;
        }
        return i === word.length;
    }
    
    let result = "";
    
    for (let word of dictionary) {
        if (isSubsequence(word, s)) {
            if (word.length > result.length || 
                (word.length === result.length && word < result)) {
                result = word;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n + n × m)，其中 n 是字典长度，m 是字符串平均长度
空间复杂度O(1)，不考虑排序的额外空间

相关题目