leetcode 524 通过删除字母匹配到字典里最长单词
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
示例2
输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"
思路
利用双指针，一个指向 dictory 下的每个单词的小标，一个指向 s 的下标，使用双循环，不断比较这两个下标对应的值，每一个 dictory[i] 遍历结束后，查看是否满足找到 s 的要求，如果满足则得到结果。
代码
/**
* @param {string} s
* @param {string[]} dictionary
* @return {string}
*/
var findLongestWord = function(s, dictionary) {
let res = '';
function wordCompare(a, b) {
let res1 = 0;
for (const c of a.split('')) {
res1 += c.charCodeAt();
}
let res2 = 0;
for (const c of b.split('')) {
res2 += c.charCodeAt();
}
return res1 > res2;
}
for (const t of dictionary) {
let sIndex = 0;
let dIndex = 0;
while (sIndex < s.length && dIndex < t.length) {
if (s[sIndex] === t[dIndex]) {
dIndex++;
}
sIndex++;
}
if (dIndex === t.length) {
if (res.length < t.length || (res.length === t.length && t < res)) {
res = t;
}
}
}
return res;
};
复杂度分析:
- 时间复杂度: O(N^2)
- 空间复杂度：O(1)