524 Longest Word in Dictionary through Deleting 通過刪除字母匹配到字典里最長單詞

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

Example:

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s and dictionary[i] consist of lowercase English letters.

題目描述:
給定一個字符串和一個字符串字典，找到字典里面最長的字符串，該字符串可以通過刪除給定字符串的某些字符來得到。如果答案不止一個，返回長度最長且字典順序最小的字符串。如果答案不存在，則返回空字符串。

示例 :

示例 1:

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

輸出:
"apple"

示例 2:

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

輸出:
"a"

說明:

所有輸入的字符串只包含小寫字母。
字典的大小不會超過 1000。
所有輸入的字符串長度不會超過 1000。

思路:

1. 先對 dictionary 按照字符串長度降序, 字典序升序排序
   然后用雙指針遍歷 dictionary, 找到第一個滿足 s 子序列的就返回
   時間復(fù)雜度 O(mnlgn), 空間復(fù)雜度 O(lgn), m 表示字符串的平均長度, n 表示字符串中字符的數(shù)量
2. 不排序直接查找是否有滿足題意的字符串
   找到之后再比較字符串的長度和字典序
   時間復(fù)雜度 O(mn), 空間復(fù)雜度 O(m), m 表示字符串的平均長度, n 表示字符串中字符的數(shù)量

代碼:
C++:

class Solution 
{
public:
    string findLongestWord(string s, vector<string>& dictionary) 
    {
        string result = "";
        for (auto &word: dictionary) if (is_subsequence(word, s)) if (word.size() > result.size() or (word.size() == result.size() and word < result)) result = word;
        return result;
    }
private:
    bool is_subsequence(string &x, string &y) 
    {
        int j = 0, m = y.size(), n = x.size();
        for (int i = 0; i < m and j < n; i++) if (x[j] == y[i]) ++j;
        return j == n;
    }
};

Java:

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String result = "";
        for (String word: dictionary) if (isSubsequence(word, s)) if (word.length() > result.length() || (word.length() == result.length() && word.compareTo(result) < 0)) result = word;
        return result;
    }
    
    private boolean isSubsequence(String x, String y) {
        int j = 0, m = y.length(), n = x.length();
        for (int i = 0; i < m && j < n; i++) if (x.charAt(j) == y.charAt(i)) ++j;
        return j == n;
    }
}

Python:

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        dictionary.sort(key=lambda x: (-len(x), x))
        for word in dictionary:
            i = 0
            for c in s:
                if c == word[i:i + 1]:
                    i += 1
            if i == len(word):
                return word
        return ""