class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
}
};
524. 通过删除字母匹配到字典里最长单词
给你一个字符串 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] 仅由小写英文字母组成相似题目
原站题解
javascript 解法, 执行用时: 104 ms, 内存消耗: 52.2 MB, 提交时间: 2023-05-30 10:01:29
/**
* @param {string} s
* @param {string[]} dictionary
* @return {string}
*/
var findLongestWord = function(s, dictionary) {
const m = s.length;
const f = new Array(m + 1).fill(0).map(() => new Array(26).fill(m));
for (let i = m - 1; i >= 0; --i) {
for (let j = 0; j < 26; ++j) {
if (s[i] === String.fromCharCode('a'.charCodeAt() + j)) {
f[i][j] = i;
} else {
f[i][j] = f[i + 1][j];
}
}
}
let res = "";
for (const t of dictionary) {
let match = true;
let j = 0;
for (let i = 0; i < t.length; ++i) {
if (f[j][t[i].charCodeAt() - 'a'.charCodeAt()] === m) {
match = false;
break;
}
j = f[j][t[i].charCodeAt() - 'a'.charCodeAt()] + 1;
}
if (match) {
if (t.length > res.length || (t.length === res.length && t.localeCompare(res) < 0)) {
res = t;
}
}
}
return res;
};
golang 解法, 执行用时: 12 ms, 内存消耗: 7 MB, 提交时间: 2023-05-30 10:01:09
func findLongestWord(s string, dictionary []string) (ans string) {
m := len(s)
f := make([][26]int, m+1)
for i := range f[m] {
f[m][i] = m
}
for i := m - 1; i >= 0; i-- {
f[i] = f[i+1]
f[i][s[i]-'a'] = i
}
outer:
for _, t := range dictionary {
j := 0
for _, ch := range t {
if f[j][ch-'a'] == m {
continue outer
}
j = f[j][ch-'a'] + 1
}
if len(t) > len(ans) || len(t) == len(ans) && t < ans {
ans = t
}
}
return
}
java 解法, 执行用时: 5 ms, 内存消耗: 43 MB, 提交时间: 2023-05-30 10:00:54
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
int m = s.length();
int[][] f = new int[m + 1][26];
Arrays.fill(f[m], m);
for (int i = m - 1; i >= 0; --i) {
for (int j = 0; j < 26; ++j) {
if (s.charAt(i) == (char) ('a' + j)) {
f[i][j] = i;
} else {
f[i][j] = f[i + 1][j];
}
}
}
String res = "";
for (String t : dictionary) {
boolean match = true;
int j = 0;
for (int i = 0; i < t.length(); ++i) {
if (f[j][t.charAt(i) - 'a'] == m) {
match = false;
break;
}
j = f[j][t.charAt(i) - 'a'] + 1;
}
if (match) {
if (t.length() > res.length() || (t.length() == res.length() && t.compareTo(res) < 0)) {
res = t;
}
}
}
return res;
}
}
python3 解法, 执行用时: 100 ms, 内存消耗: 18.3 MB, 提交时间: 2023-05-30 10:00:24
'''
动态规划
令 f[i][j] 表示字符串 s 中从位置 i 开始往后字符 j 第一次出现的位置。
在进行状态转移时，如果 s 中位置 i 的字符就是 j，那么 f[i][j]=i，
否则 j 出现在位置 i+1 开始往后，即 f[i][j]=f[i+1][j]；
因此我们要倒过来进行动态规划，从后往前枚举 i。
'''
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
m = len(s)
f = [[0] * 26 for _ in range(m)]
f.append([m] * 26)
for i in range(m - 1, -1, -1):
for j in range(26):
if ord(s[i]) == j + 97:
f[i][j] = i
else:
f[i][j] = f[i + 1][j]
res = ""
for t in dictionary:
match = True
j = 0
for i in range(len(t)):
if f[j][ord(t[i]) - 97] == m:
match = False
break
j = f[j][ord(t[i]) - 97] + 1
if match:
if len(t) > len(res) or (len(t) == len(res) and t < res):
res = t
return res
javascript 解法, 执行用时: 108 ms, 内存消耗: 49.5 MB, 提交时间: 2023-05-30 09:57:08
/**
* @param {string} s
* @param {string[]} dictionary
* @return {string}
*/
var findLongestWord = function(s, dictionary) {
dictionary.sort((word1, word2) => {
if (word1.length !== word2.length) {
return word2.length - word1.length;
} else {
return word1.localeCompare(word2);
}
});
console.log(dictionary)
for (const t of dictionary) {
let i = 0, j = 0;
while (i < t.length && j < s.length) {
if (t[i] === s[j]) {
++i;
}
++j;
}
if (i === t.length) {
return t;
}
}
return "";
};
golang 解法, 执行用时: 16 ms, 内存消耗: 7.8 MB, 提交时间: 2023-05-30 09:56:45
func findLongestWord(s string, dictionary []string) string {
sort.Slice(dictionary, func(i, j int) bool {
a, b := dictionary[i], dictionary[j]
return len(a) > len(b) || len(a) == len(b) && a < b
})
for _, t := range dictionary {
i := 0
for j := range s {
if s[j] == t[i] {
i++
if i == len(t) {
return t
}
}
}
}
return ""
}
java 解法, 执行用时: 23 ms, 内存消耗: 42.8 MB, 提交时间: 2023-05-30 09:56:31
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
Collections.sort(dictionary, new Comparator<String>() {
public int compare(String word1, String word2) {
if (word1.length() != word2.length()) {
return word2.length() - word1.length();
} else {
return word1.compareTo(word2);
}
}
});
for (String t : dictionary) {
int i = 0, j = 0;
while (i < t.length() && j < s.length()) {
if (t.charAt(i) == s.charAt(j)) {
++i;
}
++j;
}
if (i == t.length()) {
return t;
}
}
return "";
}
}
python3 解法, 执行用时: 540 ms, 内存消耗: 18.2 MB, 提交时间: 2023-05-30 09:56:12
# 排序
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
dictionary.sort(key=lambda x: (-len(x), x))
for t in dictionary:
i = j = 0
while i < len(t) and j < len(s):
if t[i] == s[j]:
i += 1
j += 1
if i == len(t):
return t
return ""
javascript 解法, 执行用时: 80 ms, 内存消耗: 45.4 MB, 提交时间: 2023-05-30 09:55:50
/**
* @param {string} s
* @param {string[]} dictionary
* @return {string}
*/
var findLongestWord = function(s, dictionary) {
let res = "";
for (const t of dictionary) {
let i = 0, j = 0;
while (i < t.length && j < s.length) {
if (t[i] === s[j]) {
++i;
}
++j;
}
if (i === t.length) {
if (t.length > res.length || (t.length === res.length && t < res)) {
res = t;
}
}
}
return res;
};
golang 解法, 执行用时: 16 ms, 内存消耗: 7.7 MB, 提交时间: 2023-05-30 09:55:29
func findLongestWord(s string, dictionary []string) (ans string) {
for _, t := range dictionary {
i := 0
for j := range s {
if s[j] == t[i] {
i++
if i == len(t) {
if len(t) > len(ans) || len(t) == len(ans) && t < ans {
ans = t
}
break
}
}
}
}
return
}
java 解法, 执行用时: 20 ms, 内存消耗: 43.1 MB, 提交时间: 2023-05-30 09:55:16
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String res = "";
for (String t : dictionary) {
int i = 0, j = 0;
while (i < t.length() && j < s.length()) {
if (t.charAt(i) == s.charAt(j)) {
++i;
}
++j;
}
if (i == t.length()) {
if (t.length() > res.length() || (t.length() == res.length() && t.compareTo(res) < 0)) {
res = t;
}
}
}
return res;
}
}
python3 解法, 执行用时: 488 ms, 内存消耗: 18.1 MB, 提交时间: 2023-05-30 09:54:58
# 双指针
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
res = ""
for t in dictionary:
i = j = 0
while i < len(t) and j < len(s):
if t[i] == s[j]:
i += 1
j += 1
if i == len(t):
if len(t) > len(res) or (len(t) == len(res) and t < res):
res = t
return res