作者:
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: