Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/09/23 12:32)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串417/719 (看更多)

https://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： --------------------------------------------- class Solution { public int longestStrChain(String[] words) { Arrays.sort(words, Comparator.comparingInt(String::length)); Map<String, Integer> map = new HashMap<>(); int ans = 0; for (String s : words) { int len = 1; for (int i = 0; i < s.length(); ++i) { // 將當前字元刪除一個並去Map找是否有剛好只刪除一個字元的較短字串 String t = s.substring(0, i) + s.substring(i + 1); len = Math.max(len, map.getOrDefault(t, 0) + 1); } map.put(s, len); ans = Math.max(ans, len); } return ans; } } --------------------------------------------- -- https://i.imgur.com/bFRiqA3.jpg