Leetcode（524）——通过删除字母匹配到字典里最长单词
题目
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：
输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”
示例 2：
输入：s = “abpcplea”, dictionary = [“a”,“b”,“c”]
输出：“a”
提示：
-
1
1
1 <= s.length <=
1000
1000
1000
-
1
1
1 <= dictionary.length <=
1000
1000
1000
-
1
1
1 <= dictionary[i].length <=
1000
1000
1000
- s 和 dictionary[i] 仅由小写英文字母组成
题解
方法一：贪心+双指针
思路
????根据题意，我们需要解决两个问题：
- 如何判断
dictionary
\textit{dictionary}
dictionary 中的字符串
t
t
t 是否可以通过删除
s
s
s 中的某些字符得到；
- 如何找到长度最长且字典序最小的字符串。
????第
1
1
1 个问题实际上就是判断
t
t
t 是否是
s
s
s 的子序列。因此只要能找到任意一种
t
t
t 在
s
s
s 中出现的方式，即可认为
t
t
t 是
s
s
s 的子序列。而当我们从前往后匹配时，可以发现每次贪心地匹配最靠前的字符（直到找到
s
s
s 中第一位与
d
i
c
t
i
o
n
a
r
y
[
x
]
[
j
]
dictionary[x][j]
dictionary[x][j] 对得上的位置）是最优决策。
假定当前需要匹配字符
c
c
c，而字符
c
c
c 在
s
s
s 中的位置
x
1
x_1
x1? 和
x
2
x_2
x2? 出现（
x
1
<
x
2
x_1 < x_2
x1?<x2?），那么贪心取
x
1
x_1
x1? 是最优解，因为
x
2
x_2
x2? 后面能取到的字符，
x
1
x_1
x1? 也都能取到，并且通过
x
1
x_1
x1? 与
x
2
x_2
x2? 之间的可选字符，更有希望能匹配成功。
????这样，我们初始化两个指针
i
i
i 和
j
j
j，分别指向
t
t
t 和
s
s
s 的初始位置。每次贪心地匹配，匹配成功则
i
i
i 和
j
j
j 同时右移，匹配
t
t
t 的下一个位置，匹配失败则
j
j
j 右移，
i
i
i 不变，尝试用
s
s
s 的下一个字符匹配
t
t
t 。
????最终如果
i
i
i 移动到
t
t
t 的末尾，则说明
t
t
t 是
s
s
s 的子序列。
????第
2
2
2 个问题可以通过遍历
dictionary
\textit{dictionary}
dictionary 中的字符串，并维护当前长度最长且字典序最小的字符串来找到。
代码实现
我自己的：
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
int maxL = -1, ptr, size_d = dictionary.size(), size_s = s.size();
for(int n = 0; n < size_d; n++){
if(maxL != -1 && (dictionary[n].size() < dictionary[maxL].size() ||
(dictionary[n].size() == dictionary[maxL].size() && dictionary[n] >= dictionary[maxL]))) continue;
ptr = 0;
for(int i = 0; i < size_s && ptr < dictionary[n].size(); i++)
if(s[i] == dictionary[n][ptr]) ptr++;
if(ptr == dictionary[n].size()) maxL = n;
}
return maxL == -1? "": dictionary[maxL];
}
};
复杂度分析
时间复杂度：
O
(
d
×
(
m
+
n
)
)
O(d×(m+n))
O(d×(m+n))，其中
d
d
d 表示
dictionary
\textit{dictionary}
dictionary 的长度，
m
m
m 表示字符串
s
s
s 的长度，
n
n
n 表示
dictionary
\textit{dictionary}
dictionary 中字符串的平均长度。我们需要遍历
dictionary
\textit{dictionary}
dictionary 中的
d
d
d 个字符串，每个字符串需要
O
(
n
+
m
)
O(n+m)
O(n+m) 的时间复杂度来判断该字符串是否为
s
s
s 的子序列。
空间复杂度：
O
(
1
)
O(1)
O(1)
方法二：双指针+排序预处理
思路
????在方法一的基础上，我们尝试通过对
dictionary
\textit{dictionary}
dictionary 的预处理，来优化第
2
2
2 个问题的处理。
??我们可以先将
dictionary
\textit{dictionary}
dictionary 依据字符串长度的降序和字典序的升序进行排序，然后从前向后找到第一个符合条件的字符串直接返回即可。
代码实现
我自己的：
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
sort(dictionary.begin(), dictionary.end(),
[](string& A, string& B){return A.size() > B.size() || (A.size() == B.size() && A < B);});
int ptr, size_d = dictionary.size(), size_s = s.size();
for(int n = 0; n < size_d; n++){
ptr = 0;
for(int i = 0; i < size_s && ptr < dictionary[n].size(); i++)
if(s[i] == dictionary[n][ptr]) ptr++;
if(ptr == dictionary[n].size()) return dictionary[n];
}
return "";
}
};
复杂度分析
时间复杂度：
O
(
d
×
m
×
l
o
g
d
+
d
×
(
m
+
n
)
)
O(d×m×logd+d×(m+n))
O(d×m×logd+d×(m+n))，其中
d
d
d 表示
dictionary
\textit{dictionary}
dictionary 的长度，
m
m
m 表示
s
s
s 的长度，
n
n
n 表示
dictionary
\textit{dictionary}
dictionary 中字符串的平均长度。我们需要
O
(
d
×
m
×
log
?
d
)
O(d \times m \times \log d)
O(d×m×logd) 的时间来排序
dictionary
\textit{dictionary}
dictionary；在最坏的情况下，我们需要
O
(
d
×
(
m
+
n
)
)
O(d \times (m+n))
O(d×(m+n)) 来找到第一个符合条件的字符串。
空间复杂度：
O
(
d
×
m
)
O(d×m)
O(d×m)，为排序的开销。
方法三：双指针+DP预处理
思路
????在方法一的基础上，我们考虑通过对字符串
s
s
s 的预处理，来优化第
1
1
1 个问题的处理。
????考虑前面的双指针的做法，我们注意到我们有大量的时间用于在
s
s
s 中找到下一个匹配字符。
????这样我们通过预处理，得到：对于字符串
s
s
s 的每一个位置，从该位置开始往后每一个字符第一次出现的位置（包括该位置）。
????我们可以使用动态规划的方法实现预处理，令
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示字符串
s
s
s 中从位置
i
i
i 开始往后字符
j
j
j 第一次出现的位置。在进行状态转移时，如果
s
s
s 中位置
i
i
i 的字符就是
j
j
j，那么
f
[
i
]
[
j
]
=
i
f[i][j]=i
f[i][j]=i，否则
j
j
j 出现在位置
i
+
1
i+1
i+1 开始往后，即
f
[
i
]
[
j
]
=
f
[
i
+
1
]
[
j
]
f[i][j]=f[i+1][j]
f[i][j]=f[i+1][j]；因此我们要反向进行动态规划，从后往前枚举
i
i
i。
这样我们可以写出状态转移方程：
f
[
i
]
[
j
]
=
{
i
,
s
[
i
]
=
j
f
[
i
+
1
]
[
j
]
,
s
[
i
]
≠
j
f[i][j]= \begin{cases} i, & s[i]=j \\ f[i+1][j], & s[i] \ne j \end{cases}
f[i][j]={i,f[i+1][j],?s[i]=js[i]?=j?
????假定下标从
0
0
0 开始，那么
f
[
i
]
[
j
]
f[i][j]
f[i][j] 中有
0
≤
i
≤
m
?
1
0 \leq i \leq m-1
0≤i≤m?1，对于边界状态
f
[
m
?
1
]
[
.
.
]
f[m-1][..]
f[m?1][..]，我们令
f
[
m
]
[
.
.
]
f[m][..]
f[m][..] 的值为
m
m
m，让
f
[
m
?
1
]
[
.
.
]
f[m-1][..]
f[m?1][..] 正常进行转移。这样如果
f
[
i
]
[
j
]
=
m
f[i][j]=m
f[i][j]=m，则表示从位置
i
i
i 开始往后不存在字符
j
j
j。
????这样，我们可以利用
f
f
f 数组，每次
O
(
1
)
O(1)
O(1) 地跳转到下一个位置，直到位置变为
m
m
m 或
t
t
t 中的每一个字符都匹配成功。
代码实现
Leetcode 官方题解：
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
const int n = s.size();
int next[26];
fill_n(next, 26, -1);
int trans[n + 1][26];
fill_n(trans[n], 26, -1);
for (int i = n - 1;0 <= i;--i) {
next[s[i] - 'a'] = i + 1;
copy_n(next, 26, trans[i]);
}
string_view ans = "";
for (const auto& e : dictionary) {
int state = 0;
for (char c : e) {
state = trans[state][c - 'a'];
if (state == -1) break;
}
if (state == -1) continue;
if (e.size() > ans.size() || e.size() == ans.size() && e < ans)
ans = e;
}
return string(ans);
}
};
我自己的（STL版本）：
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
int maxL = -1, ptr, s_size = s.size(), d_size = dictionary.size();
vector<vector<int>> s_letter(s_size, vector<int>(26, -1));
for(int n = s_size-1; n >= 0; n--){
if(n != s_size-1) s_letter[n] = s_letter[n+1];
s_letter[n][s[n]-'a'] = n;
}
for(int n = 0; n < d_size; n++){
if(maxL != -1 && (dictionary[n].size() < dictionary[maxL].size() ||
(dictionary[n].size() == dictionary[maxL].size() && dictionary[n] >= dictionary[maxL]))) continue;
ptr = 0;
for(int i = 0; i < s_size && ptr < dictionary[n].size(); i++){
i = s_letter[i][dictionary[n][ptr]-'a'];
if(i == -1) break;
ptr++;
}
if(ptr == dictionary[n].size()) maxL = n;
}
return maxL == -1? "": dictionary[maxL];
}
};
我自己的（基本数组类型）：
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
int maxL = -1, ptr, s_size = s.size(), d_size = dictionary.size();
int s_letter[s_size][26];
fill_n(s_letter[s_size-1], 26, -1);
for(int n = s_size-1; n >= 0; n--){
if(n != s_size-1) copy_n(s_letter[n+1], 26, s_letter[n]);
s_letter[n][s[n]-'a'] = n;
}
for(int n = 0; n < d_size; n++){
if(maxL != -1 && (dictionary[n].size() < dictionary[maxL].size() ||
(dictionary[n].size() == dictionary[maxL].size() && dictionary[n] >= dictionary[maxL]))) continue;
ptr = 0;
for(int i = 0; i < s_size && ptr < dictionary[n].size(); i++){
i = s_letter[i][dictionary[n][ptr]-'a'];
if(i == -1) break;
ptr++;
}
if(ptr == dictionary[n].size()) maxL = n;
}
return maxL == -1? "": dictionary[maxL];
}
};
复杂度分析
时间复杂度：
O
(
m
×
∣
Σ
∣
+
d
×
n
)
O(m \times |\Sigma|+d \times n)
O(m×∣Σ∣+d×n)，其中
d
d
d 表示
dictionary
\textit{dictionary}
dictionary 的长度，
Σ
\Sigma
Σ 为字符集，在本题中字符串只包含英文小写字母，故
∣
Σ
∣
=
26
|\Sigma|=26
∣Σ∣=26；
m
m
m 表示字符串
s
s
s 的长度，
n
n
n 表示
dictionary
\textit{dictionary}
dictionary 中字符串的平均长度。预处理的时间复杂度为
O
(
m
×
∣
Σ
∣
)
O(m \times |\Sigma|)
O(m×∣Σ∣)；判断
d
d
d 个字符串是否为
s
s
s 的子序列的事件复杂度为
O
(
d
×
n
)
O(d \times n)
O(d×n)。
空间复杂度：
O
(
m
×
∣
Σ
∣
)
O(m×∣\Sigma∣)
O(m×∣Σ∣)，为动态规划数组的开销。
|