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

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

article 2025/2/23 5:04:35

1、题目描述：

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

2、代码：

高逼格代码：

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        // 定义一个 lambda 表达式 compareStr，用于判断字典中的字符串是否是 s 的子序列
        auto compareStr = [&](const string& s, const string& dic) -> bool {
            int i = 0, j = 0; // i 遍历 s，j 遍历 dic
            while (i < s.size() && j < dic.size()) { // 双指针遍历两个字符串
                if (s[i] == dic[j]) { // 如果字符匹配，移动 dic 的指针
                    ++j;
                }
                ++i; // 始终移动 s 的指针
            }
            return j == dic.size(); // 如果 dic 被完全匹配，返回 true
        };

        // 对字典进行排序：优先按长度降序排列，如果长度相同则按字典序升序排列
        sort(dictionary.begin(), dictionary.end(),
             [](const string& a, const string& b) {
                 return (a.size() == b.size()) ? (a < b) : (a.size() > b.size());
             });

        // 遍历排序后的字典，找到第一个符合条件的字符串
        for (auto str : dictionary) {
            if (compareStr(s, str)) { // 如果当前字符串是 s 的子序列
                return str; // 返回该字符串
            }
        }

        // 如果没有找到符合条件的字符串，返回空字符串
        return "";
    }
};

普通代码：

class Solution {
public:
    // 判断字典中的字符串 dictionary 是否是字符串 s 的子序列
    bool compareStr(const string& s, const string& dictionary) {
        int i = 0, j = 0; // i 遍历 s，j 遍历 dictionary
        while (i < s.size() && j < dictionary.size()) { // 双指针遍历两个字符串
            if (s[i] == dictionary[j]) { // 如果字符匹配，移动 dictionary 的指针
                ++j;
            }
            ++i; // 始终移动 s 的指针
        }
        return j == dictionary.size(); // 如果 dictionary 被完全匹配，返回 true
    }

    // 主函数：从字典中找到最长且符合条件的字符串
    string findLongestWord(string s, vector<string>& dictionary) {
        // 如果字符串 s 为空，直接返回空字符串（题目保证 s 不为空，此检查可省略）
        if (s == "") {
            return "";
        }

        // 对字典进行排序：优先按长度降序排列，如果长度相同则按字典序升序排列
        sort(dictionary.begin(), dictionary.end(),
             [](const string& a, const string& b) {
                 if (a.size() != b.size()) // 如果长度不同，按长度降序排列
                     return a.size() > b.size();
                 return a < b; // 如果长度相同，按字典序升序排列
             });

        // 遍历排序后的字典，找到第一个符合条件的字符串
        for (auto str : dictionary) {
            if (compareStr(s, str)) { // 如果当前字符串是 s 的子序列
                return str; // 返回该字符串
            }
        }

        // 如果没有找到符合条件的字符串，返回空字符串
        return "";
    }
};