DEV Community
·
1092. 最短公共超序列
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定两个字符串str1和str2，使用动态规划找到它们的最长公共子序列，从而构建最短公共超序列，确保结果的最优性和正确性。
🎯
关键要点
- 给定两个字符串str1和str2，目标是返回包含这两个字符串作为子序列的最短字符串。
- 字符串s是字符串t的子序列，如果从t中删除一些字符（可能为0）后得到s。
- 示例1中，str1为'abac'，str2为'cab'，输出为'cabac'。
- 示例2中，str1和str2均为'aaaaaaaa'，输出为'aaaaaaaa'。
- 约束条件为1 <= str1.length, str2.length <= 1000，且字符串仅包含小写字母。
- 可以使用动态规划找到str1和str2的最长公共子序列（LCS），进而构建最短公共超序列（SCS）。
- 动态规划表dp[i][j]表示str1[0..i-1]和str2[0..j-1]的LCS长度。
- 通过比较两个字符串的字符并利用之前计算的值填充DP表。
- 回溯构建SCS，从dp[m][n]开始，依据DP表的方向添加字符。
- 处理剩余字符，确保所有字符都包含在SCS中。
- 由于回溯时字符是逆序收集的，最后需要反转结果以获得正确的SCS顺序。
➡️
