1048. Longest String Chain

Leetcode link

解题思路

本题要求我们求出给定字符串数组的最长词链；词链中每一个元素都是后一个元素的前身；前身指的是在给定字符串不改变顺序的情况下删除任意一个字符构成的新字符串

首先，由于词链中元素的长度一定是从小到大且每个元素长度都是前一个长度加一，所以我们需要先对 words 排序

排完序之后，我们考虑动态规划的方法，创建一个数组 dp，其中 dp[i] 表示排序后的 words 数组中第 i 个元素的最长词链长度

有了 dp 之后，我们可以方便的得出，假设有个新字符串 words[j]，且它是 words[i] 的前身，则 dp[i] = max(dp[i], dp[j] + 1)

最后，如果字符串 a 是 b 的前身，要满足两个条件：

• a 的长度只能是 b 的长度减一
• a 中的字符必须按顺序出现在 b 中

C++

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b){
            return a.size() < b.size();
        });
        int len = words.size();
        vector<int> dp(len, 1);
        int res = 1;

        for(int i = 0;i < len;i++) {
            for(int j = i - 1;j >= 0;j--) {
                if(isPredecessor(words[j], words[i])) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }

        return res;
    }

    bool isPredecessor(const string& s1, const string& s2) {
        if(s1.size() != s2.size() - 1) {
            return false;
        }

        int i = 0;
        for(int j = 0;j < s2.size();j++) {
            if(s1[i] == s2[j]) {
                i++;
            }
        }
        return i == s1.size();
    }
};

Javascript

/**
 * @param {string[]} words
 * @return {number}
 */
var longestStrChain = function (words) {
    words.sort((a, b) => a.length - b.length);
    let len = words.length;
    let dp = new Array(len).fill(1);
    let res = 1;

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

var isPredecessor = function (str1, str2) {
    // predecessor 最多允许少一个字符
    if (str1.length !== str2.length - 1) {
        return false;
    }

    let i = 0;
    for (let j = 0; j < str2.length; j++) {
        if (str1[i] === str2[j]) {
            i++;
        }
    }

    return i === str1.length;
};