楼主:
Rushia (みけねこ的鼻屎)
2023-09-23 12:32:23https://leetcode.com/problems/longest-string-chain/description
1048. Longest String Chain
给你一群字串 words,如果比较短的字串可以透过添加一个字串来得到比较长的字串,这
两个字串我们称他为一个 Chain,求出这些字串可以组成的最长 Chain 长度为多少。
思路:
1.可以用动态规划来找出最长的 Chain,一个字串 s 和 t 要变成 Chain 只需检查所有
比 s 短的字串是否和 s 只差一个字符,我们可以把字串透过 substr 一个一个切,
然后去检查前面的较短是否满足,是的话 s 的长度就是 t 的长度 + 1。
2.因为 words 不是序列或子字串,他顺序可以颠倒,所以我们先把原字串阵列依照长度
排序再处理。
Java Code: