524. Longest Word in Dictionary through Deleting

Leetcode 问题: 524. Longest Word in Dictionary through Deleting
Categories:
Tags:

题目

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

给一个字串 s，以及一个字串字典阵列 dictionary，找出 dictionary 中能够符合字串 s 的子字串，且字串是最长的

如果有字串 长度相同 的 子字串，按照字母大小排序（a < z），将排序中最小的字串回传

如果没有找到任何子字串，则回传空字串

Example 1

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Example 2

Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

答案

JavaScript

1. 字串字典先排序

字典字串先排序，字串长度越长 排在越前面，等等优先检查

若一找到一符合的子字串，即可马上跳出，因为后面一定没有比目前更长的字串了

/**
 * @param {string} searchString
 * @param {string[]} searchDictionary
 * @return {string}
 */
var findLongestWord = function(searchString, searchDictionary) {

    // 长度较长的字串排序在前面，长度一样的字串，按照字母顺序排序
    searchDictionary.sort((string1, string2) => {
        if (string1.length == string2.length) {
            // 两者长度相同，比较字母顺序
            if (string1 < string2) {
                // string1 字母排序较前，优先排序
                return -1;
            } else {
                // string2 字母排序较前，优先排序
                return 1;
            }
        }

        if (string1.length > string2.length) {
            // string 1 较长，较长的排在前面
            return -1;
        } else {
            // string 2 较长，较长的排在前面
            return 1;
        }
    });

    // 最长的字串
    let longestString = '';
    for (let searchStringIndex in searchDictionary) {
        // 候选字
        let candidateString = searchDictionary[searchStringIndex];
        if (candidateString.length > searchString.length) {
            // 如果「候选字串长度」小于「搜寻字串长度」，无法成为子字串，找下一个
            continue;
        }

        // 设定子字串搜寻指标
        let pointerSearchString = 0;
        let pointerCandidateString = 0;

        while (pointerSearchString < searchString.length && pointerCandidateString < candidateString.length) {
            // 若「搜寻字串指标」与「字典字串指标」都还没超过字串长度
            if (searchString[pointerSearchString] == candidateString[pointerCandidateString]) {
                // 「搜寻字串字」与「字典字串的字」相同，字典自往后移动继续比对
                pointerCandidateString++;
            }
            // 移动搜寻字串的字串指标
            pointerSearchString++;
        }

        if (pointerCandidateString == candidateString.length) {
            // 若候选字是完整比对完，确定是子字串，则表示找到候选字了，跳出后面不需要再检查了
            longestString = candidateString;
            break;
        }
    }

    return longestString;
};

2. 字串字典先排序，将 Subsequence 重构可读性更高

/**
 * @param {string} searchString
 * @param {string[]} searchDictionary
 * @return {string}
 */
var findLongestWord = function(searchString, searchDictionary) {

    // 长度较长的字串排序在前面，长度一样的字串，按照字母顺序排序
    searchDictionary.sort((string1, string2) => {
        if (string1.length == string2.length) {
            // 两者长度相同，比较字母顺序
            if (string1 < string2) {
                // string1 字母排序较前，优先排序
                return -1;
            } else {
                // string2 字母排序较前，优先排序
                return 1;
            }
        }

        if (string1.length > string2.length) {
            // string 1 较长，较长的排在前面
            return -1;
        } else {
            // string 2 较长，较长的排在前面
            return 1;
        }
    });

    // 最长的字串
    let longestString = '';
    for (let searchStringIndex in searchDictionary) {
        // 候选字
        let candidateSubsequenceString = searchDictionary[searchStringIndex];

        // 确认字串是否是 Subsequence
        let isSubsequenceResult = isSubsequence(searchString, candidateSubsequenceString);

        if (isSubsequenceResult) {
            // 若候选字是完整比对完，确定是子字串，则表示找到候选字了，跳出后面不需要再检查了
            longestString = candidateSubsequenceString;
            break;
        }
    }

    return longestString;
};


var isSubsequence = function(searchString, candidateSubsequenceString) {
    // 预设不是子字串
    let isSubsequenceResult = false;

    if (candidateSubsequenceString.length > searchString.length) {
        // 如果「候选字串长度」小于「搜寻字串长度」，无法成为子字串
        return isSubsequenceResult;
    }
    // 设定子字串搜寻指标
    let pointerSearchString = 0;
    let pointerCandidateString = 0;
    while (pointerSearchString < searchString.length && pointerCandidateString < candidateSubsequenceString.length) {
        // 若「搜寻字串指标」与「字典字串指标」都还没超过字串长度
        if (searchString[pointerSearchString] == candidateSubsequenceString[pointerCandidateString]) {
            // 「搜寻字串字」与「字典字串的字」相同，字典自往后移动继续比对
            pointerCandidateString++;
        }
        // 移动搜寻字串的字串指标
        pointerSearchString++;
    }

    if (pointerCandidateString == candidateSubsequenceString.length) {
        // 若候选字是完整比对完，确定是子字串，则表示找到子字串了
        isSubsequenceResult = true;
    }

    return isSubsequenceResult;
}

3. 字串字典不先排序

/**
 * @param {string} searchString
 * @param {string[]} searchDictionary
 * @return {string}
 */
var findLongestWord = function(searchString, searchDictionary) {

    // 最长的字串
    let longestString = '';
    for (let searchStringIndex in searchDictionary) {
        // 候选字
        let candidateSubsequenceString = searchDictionary[searchStringIndex];

        if (longestString.length > candidateSubsequenceString.length
            || (longestString.length == candidateSubsequenceString.length && longestString < candidateSubsequenceString) ){
            // 若原本找的「最长子字串」长度大于「候选字串」：不用找，因为只需要找出最长的
            // 若原本找的「最长子字串」字母顺序比「候选字串」较前：不用找，因为长度一样，要找字母排序较前的
            continue;
        }

        // 确认字串是否是 Subsequence
        let isSubsequenceResult = isSubsequence(searchString, candidateSubsequenceString);

        if (isSubsequenceResult) {
            // 若候选字是完整比对完，确定是子字串，则表示找到候选字了
            longestString = candidateSubsequenceString;
        }
    }

    return longestString;
};


var isSubsequence = function(searchString, candidateSubsequenceString) {
    // 预设不是子字串
    let isSubsequenceResult = false;

    if (candidateSubsequenceString.length > searchString.length) {
        // 如果「候选字串长度」小于「搜寻字串长度」，无法成为子字串
        return isSubsequenceResult;
    }
    // 设定子字串搜寻指标
    let pointerSearchString = 0;
    let pointerCandidateString = 0;
    while (pointerSearchString < searchString.length && pointerCandidateString < candidateSubsequenceString.length) {
        // 若「搜寻字串指标」与「字典字串指标」都还没超过字串长度
        if (searchString[pointerSearchString] == candidateSubsequenceString[pointerCandidateString]) {
            // 「搜寻字串字」与「字典字串的字」相同，字典自往后移动继续比对
            pointerCandidateString++;
        }
        // 移动搜寻字串的字串指标
        pointerSearchString++;
    }

    if (pointerCandidateString == candidateSubsequenceString.length) {
        // 若候选字是完整比对完，确定是子字串，则表示找到子字串了
        isSubsequenceResult = true;
    }

    return isSubsequenceResult;
}

参考资料