题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting

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

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

示例

示例 1：

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

示例 2：

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

答案1

自己写的，基本的暴力破解的思想

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 */
var findLongestWord = function(s, dictionary) {
    const num=dictionary.length;
    const arr=s;
    let [maxindex,maxvalue]=[-1,0];
    for(let i=0;i<num;i++){
       const subarr=dictionary[i];
       let m,n;
       m=n=0;
       while(m<arr.length&&n<subarr.length){
           if(arr[m]==subarr[n]){
               m++;
               n++;
           }else{
               m++;
           }
       }
       if(n==subarr.length){
           if(maxvalue<dictionary[i].length){
               [maxindex,maxvalue]=[i,dictionary[i].length];
           }
           if(maxvalue===dictionary[i].length){
               if(dictionary[maxindex]>dictionary[i]){
                   [maxindex,maxvalue]=[i,dictionary[i].length];
               }
           }
       }
    }
    if(maxindex!=-1){
        return dictionary[maxindex];
    }else{
        return '';
    }
};

答案2

1. 按照字符串长度降序、字典序先将字典排序
2. 在字典中逐个检验字符串是否满足条件
3. 检验时，用双指针遍历来判断

const findLongestWord = (s, dictionary) => {
    // 按照字符串长度降序、字典序排序
    dictionary.sort((a, b) => (a.length === b.length ? a.localeCompare(b) : b.length - a.length));
    const lenS = s.length;

    for (const word of dictionary) {
        // 两个指针
        let [S, W] = [0, 0];
        const lenW = word.length;
        while (S < lenS && W < lenW) {
            if (s[S] === word[W]) W++;
            S++;
        }
        // W指针走到头说明word匹配完成
        if (W === lenW) return word;
    }
    return '';
};

答案链接;

Daily-question-of-Leetcode/2021-9-14-524. 通过删除字母匹配到字典里最长单词.md at master · HDU-Coder-X/Daily-question-of-Leetcode · GitHub