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

刷题记录
留言

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

题目

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

1
2
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

示例 2：

1
2
输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

提示：

  • 1 <= s.length <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • s 和 dictionary[i] 仅由小写英文字母组成

方法一：排序+双指针

比较直接简单的思路，就是利用自定义sort函数，满足最长、字典序最小的要求，再用双指针遍历每一个单词，得到的第一个解就是该题目的解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = dictionary.size();
        // 对词典进行排序，优先按照长度从大到小排，如果长度相同按字典序从小到大排
        sort(dictionary.begin(),dictionary.end(),[&](string s1,string s2){
            if(s1.size()!=s2.size()){
                return s1.size()>s2.size();
            }else{
                return s1<s2;
            }
        });
        string ans;
        // 对于排好序的词典中的单词，第一个符合要求的就可以返回。
        for(auto & word : dictionary){
            int i=0,j=0;
            // 双指针解法 匹配上时两个指针同时移动，没匹配上s指针单独移动
            while(i<s.size() && j<word.size()){
                if(word[j]==s[i]){
                    i++;
                    j++;
                }else{
                    i++;
                }
            }
            // 如果用来匹配word的指针走到头，说明全部匹配了。
            if(j==word.size()){
                ans = word;
                break;
            }
        }
        return ans;
    }
};

方法二： 双指针+维护最优解

一个贪心思路：当s中存在两个相同字符和词典中的单词匹配时，优先选择匹配靠前的字符。

该方法较方法一时间复杂度高

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = dictionary.size();
        
        string ans;
        // 遍历每一个单词
        for(auto & word : dictionary){
            int i=0,j=0;
            // 双指针解法 匹配上时两个指针同时移动，没匹配上s指针单独移动
            while(i<s.size() && j<word.size()){
                if(word[j]==s[i]){
                    i++;
                    j++;
                }else{
                    i++;
                }
            }
            // 如果用来匹配word的指针走到头，说明全部匹配了。
            // 此时要进行对最优解的维护
            if(j==word.size()){
                if(word.size()>ans.size() || (word.size()==ans.size()&& word<ans))
                    ans = word;
            }
        }
        return ans;
    }
};

方法三：动态规划

针对方法2进行改进，使用DP数组，对双指针遍历部分进行简化。

DP数组虽然是二维，但是一层的长度只要涵盖26个英文字母就好。状态转移方程为：

其含义是，对于s中的第$i$个位置，字符j将会在$dp[i][j]$处出现，所以显然当$s[i]=j$时，出现为$i$，否则就看看$i+1$是否知道位置。

因此该DP数组要倒退实现。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<vector<int>> dp(n+1,vector<int>(26,n));
        
        // 倒序构成dp数组
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<26;j++){
                if('a'+j==s[i]){
                    dp[i][j]=i;
                }else{
                    dp[i][j] = dp[i+1][j];
                }
                //cout << dp[i][j] << " ";
            }
            //cout << endl;
        }
        string ans="";
        // 遍历每一个单词
        for(auto & word : dictionary){
            bool match=true;
            int i=0;
            for(auto & c : word){
                if(dp[i][c-'a']==n){
                    match=false;
                    break;
                }else{
                    i = dp[i][c-'a']+1;
                }
            }

            // 如果用来匹配word的指针走到头，说明全部匹配了。
            // 此时要进行对最优解的维护
            if(match){
                if(word.size()>ans.size() || (word.size()==ans.size()&& word<ans))
                    ans = word;
            }
        }
        return ans;
    }
};