LeetCode解题报告（299)-- 524. Longest Word in Dictionary through Deleting

Problem

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

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

Output: 
"apple"

Example 2:

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

Output: 
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

---

Analysis

  题目给出一个字符串s和一个字典d，问通过对s中的字符进行删除，能够匹配到的字典中最长的字符串。对s来说，删除的字符越少越好，所以对d中的字符串来说是越长越好。所以我们可以先对d按照字符串的长度进行排序。

  因为顺序也要匹配，所以没有办法像之前那样用map统计出现的次数和种类来判断，只能把字符串遍历一遍匹配。对d中的每个单词str，我们遍历字符串s，然后再用一个下标idx指向str的开头，每当匹配一个字符，idx自增，如果遍历完之后idx是str的长度，说明整个字符串匹配成功。又因为我们的d是排好序的，所以一旦匹配，就是答案，直接return即可。

---

Solution

  无

---

Code

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        sort(d.begin(), d.end(), [](string a, string b) {
            if (a.size() == b.size()) {
                return a < b;
            }
            return a.size() > b.size();
        });
        
        for (string str: d) {
            int idx = 0;
            for (char c: s) {
                if (idx < str.size() && c == str[idx]) {
                    idx++;
                }
            }
            if (idx == str.size()) {
                return str;
            }
        }
        return "";
    }
};

---

Summary

  这道题目的分享到这里，谢谢您的支持！