最短公共超序列 (Shortest Common Supersequence, SCS)

题目描述:

给定两个字符串 A 和 B，找出这两个字符串的最短公共超序列的长度。超序列是指包含两个字符串作为子序列的最短字符串。

输入:

• A: 字符串 (1 <= A.length <= 1000)
• B: 字符串 (1 <= B.length <= 1000)

输出:

• 整数: 最短公共超序列的长度

解题思路:

我们可以通过求解 A 和 B 的最长公共子序列 (LCS) 来简化问题。A 和 B 的最短公共超序列长度为 A.length + B.length - LCS(A, B)。

步骤:

1. 计算 A 和 B 的最长公共子序列的长度。

2. 使用公式 A.length + B.length - LCS(A, B) 计算最短公共超序列的长度。

   测试数据:

   输入

   
   abcac
   cab

   输出

   5