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;
}

參考資料