1048. 最长字符串链.md

1048. 最长字符串链

• 哈希表 + 广义邻居(效率很低, 368 ms)

function longestStrChain(words: string[]): number {

    let maxLink: number = 1,
        map: Map<string, number> = new Map<string, number>();

    words.sort((aWord, bWord) => aWord.length - bWord.length);

    for (let i = 0; i < words.length; ++i) {
        let currentLink: number = 1;
        if (words[i].length !== 1) {
            const confusionWords = getConfusionWords(words[i]);
            for (let j = 0; j < confusionWords.length; ++j) {
                currentLink = Math.max(currentLink, (map.get(confusionWords[j]) || 0) + 1);
            }
        }
        maxLink = Math.max(maxLink, currentLink);
        const nextWords = getNextWords(words[i]);
        nextWords.forEach(nextWord => map.set(nextWord, currentLink));
    }

    return maxLink;
};

function getNextWords(word: string): string[] {
    const words: string[] = ["*", ...word],
        results: string[] = [];
    let index: number = 0;

    do {
        results.push(words.join(''));
        [words[index], words[index + 1]] = [words[index + 1], words[index]];
        ++index;
    } while (index <= word.length);

    return results;
}

function getConfusionWords(word: string): string[] {

    const results: string[] = [],
        words: string[] = [...word];

    for (let i = 0; i < words.length; ++i) {
        const ch: string = words[i];
        words[i] = '*';
        results.push(words.join(''));
        words[i] = ch;
    }

    return results;
}

• 动态规划(效率高, 124 ms)

function longestStrChain(words: string[]): number {

    let maxLink: number = 1;

    const dp: number[] = new Array(words.length).fill(1);

    words.sort((aWord, bWord) => aWord.length - bWord.length);

    for (let i = 1; i < words.length; ++i) {
        for (let j = i - 1; j >= 0 && words[j].length + 1 >= words[i].length; --j) {
            if (isPredecessor(words[j], words[i])) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLink = Math.max(maxLink, dp[i]);
    }

    return maxLink;
};

function isPredecessor(leftWord: string, rightWord: string): boolean {

    if (leftWord.length + 1 !== rightWord.length) {
        return false;
    }

    let i: number = 0, j: number = 0;

    while (j - i <= 1 && j < rightWord.length) {
        if (leftWord[i] === rightWord[j]) {
            ++i, ++j;
        } else {
            ++j;
        }
    }

    return i === leftWord.length;
}

• 哈希表 (效率一般, 216ms)

function longestStrChain(words: string[]): number {

    let maxLink: number = 1;

    const map: Map<string, number> = new Map<string, number>();

    words.sort((aWord, bWord) => aWord.length - bWord.length);

    for (let i = 0; i < words.length; ++i) {
        const currentLink: number = getMaxLink(words[i], map);
        map.set(words[i], currentLink);
        maxLink = Math.max(maxLink, currentLink);
    }

    return maxLink;
};

function getMaxLink(word: string, map: Map<string, number>): number {

    let maxLink: number = 1,
        words: string[] = [...word];

    for (let i = 0; i < words.length; ++i) {
        const ch: string = words[i];
        words.splice(i, 1);
        maxLink = Math.max(maxLink, (map.get(words.join('')) || 0) + 1);
        words.splice(i, 0, ch);
    }

    return maxLink;
}