1048.最长字符串链.md

1048.最长字符串链

/*
 * @lc app=leetcode.cn id=1048 lang=typescript
 *
 * [1048] 最长字符串链
 */

// @lc code=start

// @lc code=end

解法 1: 动态规划

function longestStrChain(words: string[]): number {
  words.sort((a, b) => a.length - b.length)
  const n = words.length,
    dp: number[] = new Array(n).fill(1)
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      let cnt = 0
      const a = words[i],
        b = words[j]
      if (a.length === b.length) continue
      for (let i = 0, j = 0; i < b.length; i++) {
        if (b[i] !== a[j]) cnt++
        else j++
      }
      if (cnt === 1) {
        dp[j] = Math.max(dp[j], dp[i] + 1)
      }
    }
  }
  return Math.max(...dp)
}

解法 2: 动态规划优化

function longestStrChain(words: string[]): number {
  words.sort((a, b) => a.length - b.length)
  const dp = new Map<string, number>()
  let res = 1
  for (let word of words) {
    let ans = 1
    for (let i = 0; i < word.length; i++) {
      const a = word.slice(0, i) + word.slice(i + 1)
      ans = Math.max(ans, (dp.get(a) ?? -Infinity) + 1)
    }
    dp.set(word, ans)
    res = Math.max(res, ans)
  }
  return res
}

Case

test.each([
  { input: { words: ['a', 'b', 'ba', 'bca', 'bda', 'bdca'] }, output: 4 },
  { input: { words: ['xbc', 'pcxbcf', 'xb', 'cxbc', 'pcxbc'] }, output: 5 },
  { input: { words: ['abcd', 'dbqca'] }, output: 1 },
])('input: words = $input.words', ({ input: { words }, output }) => {
  expect(longestStrChain(words)).toEqual(output)
})