Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間9月前 (2025/02/28 15:44)推噓0(0推 0噓 1→)

https://leetcode.com/problems/shortest-common-supersequence 1092. Shortest Common Supersequence 給你兩個字串，求出他們的最短共同超序列，超序列定義成刪除其中的一些字元後可以得到字串s。思路: 1.先找出最長共通子序列，這個序列的元素是共同元素，所以這些元素不必出現在res 兩次。 2.透過回溯的方式可以還原出LCS字串，如果s1和s2的尾巴元素相同則一定是LCS，直接 append就可以，如果不同，透過檢查DP可以知道s1和s2的尾巴元素哪個不包含在LCS 裡面(把i刪了會比把j刪了長表示i不在LCS)，那個不包含的元素我們需要將他加入超序列。 3.因為是回溯還原的所以結果要再倒序一次。 Java Code: -------------------------------------------------------------- class Solution { public String shortestCommonSupersequence(String str1, String str2) { int m = str1.length(), n = str2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } StringBuilder result = new StringBuilder(); int i = m, j = n; while (i > 0 && j > 0) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { result.append(str1.charAt(i - 1)); i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { result.append(str1.charAt(i - 1)); i--; } else { result.append(str2.charAt(j - 1)); j--; } } while (i > 0) { result.append(str1.charAt(i - 1)); i--; } while (j > 0) { result.append(str2.charAt(j - 1)); j--; } return result.reverse().toString(); } } -------------------------------------------------------------- -- https://i.imgur.com/SLF19AR.jpeg