题目描述
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
示例 2：
输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"
提示：
1 <= s.length <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000s 和 dictionary[i] 仅由小写英文字母组成
解法
方法一：判断子序列
思考
要从字典里选一个可通过删除 \(s\) 中字符得到的最长串，并列时取字典序最小。对 \(s\) 的每个子序列查字典不现实。
反过来对字典中每个词判断它是否为 \(s\) 的子序列，双指针一次扫描即可。同时用长度优先、字典序其次的规则维护当前最优。字典大小与词长均不大，总代价可接受。
我们定义一个函数 \(check(s, t)\)，用于判断字符串 \(s\) 是否是字符串 \(t\) 的子序列。我们可以使用双指针的方法，初始化两个指针 \(i\) 和 \(j\) 分别指向字符串 \(s\) 和字符串 \(t\) 的开头，然后不断移动指针 \(j\)，如果 \(s[i]\) 和 \(t[j]\) 相等，则移动指针 \(i\)，最后判断 \(i\) 是否等于 \(s\) 的长度即可。若 \(i\) 等于 \(s\) 的长度，则说明 \(s\) 是 \(t\) 的子序列。
我们初始化答案字符串 \(ans\) 为空字符串，然后遍历数组 \(dictionary\) 中的每个字符串 \(t\)，如果 \(t\) 是 \(s\) 的子序列，并且 \(t\) 的长度大于 \(ans\) 的长度，或者 \(t\) 的长度等于 \(ans\) 的长度且 \(t\) 字典序小于 \(ans\)，则更新 \(ans\) 为 \(t\)。
时间复杂度 \(O(d \times (m + n))\)，其中 \(d\) 是字符串列表的长度，而 \(m\) 和 \(n\) 分别是字符串 \(s\) 的长度和字符串列表中字符串的平均长度。空间复杂度 \(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
def check(s: str, t: str) -> bool:
m, n = len(s), len(t)
i = j = 0
while i < m and j < n:
if s[i] == t[j]:
i += 1
j += 1
return i == m
ans = ""
for t in dictionary:
if check(t, s) and (len(ans) < len(t) or (len(ans) == len(t) and ans > t)):
ans = t
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String ans = "";
for (String t : dictionary) {
int a = ans.length(), b = t.length();
if (check(t, s) && (a < b || (a == b && t.compareTo(ans) < 0))) {
ans = t;
}
}
return ans;
}
private boolean check(String s, String t) {
int m = s.length(), n = t.length();
int i = 0;
for (int j = 0; i < m && j < n; ++j) {
if (s.charAt(i) == t.charAt(j)) {
++i;
}
}
return i == m;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
string ans = "";
auto check = [&](const string& s, const string& t) {
int m = s.size(), n = t.size();
int i = 0;
for (int j = 0; i < m && j < n; ++j) {
if (s[i] == t[j]) {
++i;
}
}
return i == m;
};
for (auto& t : dictionary) {
int a = ans.size(), b = t.size();
if (check(t, s) && (a < b || (a == b && ans > t))) {
ans = t;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func findLongestWord(s string, dictionary []string) string {
ans := ''
check := func(s, t string) bool {
m, n := len(s), len(t)
i := 0
for j := 0; i < m && j < n; j++ {
if s[i] == t[j] {
i++
}
}
return i == m
}
for _, t := range dictionary {
a, b := len(ans), len(t)
if check(t, s) && (a < b || (a == b && ans > t)) {
ans = t
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function findLongestWord(s: string, dictionary: string[]): string {
const check = (s: string, t: string): boolean => {
const [m, n] = [s.length, t.length];
let i = 0;
for (let j = 0; i < m && j < n; ++j) {
if (s[i] === t[j]) {
++i;
}
}
return i === m;
};
let ans: string = '';
for (const t of dictionary) {
const [a, b] = [ans.length, t.length];
if (check(t, s) && (a < b || (a === b && ans > t))) {
ans = t;
}
}
return ans;
}
|
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 | impl Solution {
pub fn find_longest_word(s: String, dictionary: Vec<String>) -> String {
let mut ans = String::new();
for t in dictionary {
let a = ans.len();
let b = t.len();
if Self::check(&t, &s) && (a < b || (a == b && t < ans)) {
ans = t;
}
}
ans
}
fn check(s: &str, t: &str) -> bool {
let (m, n) = (s.len(), t.len());
let mut i = 0;
let mut j = 0;
let s: Vec<char> = s.chars().collect();
let t: Vec<char> = t.chars().collect();
while i < m && j < n {
if s[i] == t[j] {
i += 1;
}
j += 1;
}
i == m
}
}
|