题目描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

样例

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

注意

• 所有输入的字符串只包含小写字母。
• 字典的大小不会超过 1000。
• 所有输入的字符串长度不会超过 1000。

算法

(枚举) $O(nm)$

1. 枚举字典中的每一个单词，尝试和给定的字符串做匹配。
2. 匹配时，固定两个变量 i 和 j 分别表示给定的字符串和字典中的单词。
3. 若 s[i] == word[j]，则 i 和 j 均向后移动。否则 i 单独向后移动。
4. 最后判断 j 若到了单词末尾，则说明匹配成功，更新答案即可。

时间复杂度

• 共 $m$ 个单词，每次匹配的时间复杂度为 $O(n)$，即给定字符串的长度，故总时间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    bool check(const string &s, const string &word) {
        int n = s.length(), m = word.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] == word[j]) {
                i++;
                j++;
            }
            else
                i++;
        }
        return j == m;
    }

    string findLongestWord(string s, vector<string>& d) {
        string ans = "";
        for (string &word : d) {
            if (check(s, word)) {
                if (ans.length() < word.length())
                    ans = word;
                else if (ans.length() == word.length())
                    ans = min(ans, word);
            }
        }

        return ans;
    }
};