14.3 双序列问题

Kesa...大约 10 分钟

双序列问题有两个或多个输入序列, 状态方程有两个参数, $f(i,j)$ ,需要找出 $f(i,j)$ 和 $f(i-1,j), f(i,j-1), f(i-1,j-1)$ 的关系.

14.3.1 问题95: 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

14.3.1.1 分析&题解

解决此问题需要多步, 每步有两个选择(是否添加字符构成公共子串), 若求全部子串则用回溯法, 求最优解使用动态规划.

状态转移方程

两个字符串S1[0,m-1], S2[0,n-1], 若 $f(i,j)$ 为S1[0,i]和S2[0,j]的最长公共子串长, 那么 $f(m-1,n-1)$ 就是最优解.

当选择两个字符S1[i]和S2[j]时:

若S1[i] == S2[j]: 那么添加此字符后最长公共子串长度加一, 即 $f(i,j)=f(i-1,j-1)+1$
若S1[i] != S2[j]: 那么此时这两个字符不可能在 $f(i,j)$ 代表的最长公共子串中, 此时: $f(i,j)=max(f(i-1,j),f(i,j-1))$

最后得到状态转移方程:

$f(i,j)=\begin{cases}f(i-1,j-1) & S_1[i]=S_2[j] \\ max(f(i-1,j),f(i,j-1)) & S_1[i] \ne S_2[j] \end{cases}$

$f(-1,j)$ 表示空字符串和S2的公共子串长度为0.

使用二维数组int[m+1][n+1]表示 $f(i,j)$ 的值, 首行和首列用于表示i或j为-1的情形.

迭代二维数组 SC: O(mn)

TC: O(mn)

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    
    // 缓存
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := range text1 {
        for j := range text2 {
            if text1[i] == text2[j] {
                dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            }
        }
    }

    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

迭代 SC: O(min(m,n)) 二维数组只保留两行

计算 $f(i,j)$ 只需要 $f(i-1,j-1), f(i,j-1),f(i-1,j)$ 三个值, 那么只需要保留两行即可. 列数为两个字符串长度的较大值.

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    if m < n {
        return longestCommonSubsequence(text2, text1)
    }

    // 缓存
    dp := make([][]int, 2)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // 计算
    for i := range text1 {
        for j := range text2 {
            if text1[i] == text2[j] {
                dp[(i+1)%2][j+1] = dp[i%2][j] + 1
            } else {
                dp[(i+1)%2][j+1] = max(dp[i%2][j+1], dp[(i+1)%2][j])
            }
        }
    }

    return dp[m%2][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

迭代一维数组

将两行的二维数组换成一维数组, 辅助空间减半.

每个位置保存原来的上下两个信息, 对于dp[j+1]:

计算前: 保存的是 $f(i-1,j)$
计算后: 保存的是 $f(i,j)$

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    if m < n {
        return longestCommonSubsequence(text2, text1)
    }

    // 缓存
    dp := make([]int, n+1)
    
    // 计算
    for i := range text1 {
        prev := dp[0] // prev is f(i-1, j-1)
        for j := range text2 {
            cur := 0 // cur is f(i,j)
            if text1[i] == text2[j] {
                cur = prev + 1 // f(i,j) = f(i-1,j-1) + 1
            } else {
                // f(i,j) = max(f(i,j-1), f(i-1, j))
                // dp[j] is f(i, j-1)
                // dp[j+1] is f(i-1, j)
                cur = max(dp[j], dp[j+1]) 
            }
            
            // prev is f(i-1, j)
            prev = dp[j+1]
            // d[j+1] is f(i, j)
            dp[j+1] = cur
        }
    }

    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

14.3.2 问题96: 字符串交织

LCR 096. 交错字符串open in new window

给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。
两个字符串 s 和 t 交织的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交织是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
提示：a + b 意味着字符串 a 和 b 连接。
示例 1：
img
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true
提示：
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

14.3.2.1 分析&题解

从S1和S2中选择字符构成S3需要多步, 每步都有两个(选择S1或S2)选择, 若求所有的交织结果, 使用回溯法.

但问题要求能不能,即解的数目大于0, 使用动态规划.

状态转移方程

字符串S1[0,m-1], S2[0,n-1], 若 $f(i,j)$ 表示子串 $S_1[0,i], S_2[0,j]$ 能否交织成的字符串S_3[0,i+j+1], $f(m-1, n-1)$ 就是问题的解.

对于字符S3[i+j+1]:

和S1[i]相同, 那么如果S1[0,i-1]能和S2[0,j]交织成S3[0,i+j], S1[0,i]和S2[0,j]就可以交织成S3[0,j+i+1] 即 $f(i,j)=f(i-1,j)$
和S2[j]相同, 类似的有: $f(i,j)=f(i,j-1)$

得出公式: $f(i,j)=((S_1[i]=S_3[i]) &f (i-1,j))|((S_2[j]=S_3[j]) &f(i,j-1)) $

采用自下而上的迭代法解决, 那么最小问题的解是已知的:

$f(-1,-1)$ 表示空字符串相交织是否能得到空字符串, 一定为T
$f(-1,j)$ 表示空字符串和S2, 取决于 S2==S3
$f(i,-1)$ 空字符串和S1, 取决于S1==S3

那么由初始值可以得出一个二维数组, 再由状态转换方程去计算剩下的值.

S1\S2	-1	0	1	2	n
-1	T	S2[0,0] == S3[0,0]	S2[0,1] == S3[0,1]	S2[0,2] == S3[0,2]	S2[0,n-1] == S3[0,n-1]
0	S1[0,0] == S3[0,0]
1	S1[0,1] == S3[0,1]
2	S1[0,2] == S3[0,2]
...
m	S1[0,m-1] == S3[0,m-1]				`dp[m][n]`

剩下的数值由状态转移公式计算:$f(i,j)=((S_1[i]=S_3[i]) &f (i-1,j))|((S_2[j]=S_3[j]) &f(i,j-1)) $,

即dp[i+1][j+1] = (c1 == c3 && dp[i][j+1]) || (c2 == c3 && dp[i+1][j])

最终结果就是 $f(m-1,n-1)$ , 即二维数组的dp[m][n]

迭代+二维数组

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    // 边界
    if m+n != len(s3) {
        return false
    }
    
    // 缓存, 二维数组
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }

    // 最小问题, 初始值
    dp[0][0] = true
    for i := 1; i < m+1; i++ {
        dp[i][0] = s1[:i] == s3[:i]
    } 
    for i := 1; i < n+1; i++ {
        dp[0][i] = s2[:i] == s3[:i]
    }

    // 计算
    for i, c1 := range s1 {
        for j, c2 := range s2 {
            c3 := rune(s3[i+j+1])
            dp[i+1][j+1] = (c1 == c3 && dp[i][j+1]) || (c2 == c3 && dp[i+1][j])
        }
    }

    return dp[m][n]
}

迭代+一维数组

由于计算 $f(i,j)$ 只使用 $f(i-1,j), f(i,j-1)$ , 可以将二维数组优化成两行.

进一步优化, 计算 $f(i,j+1)$ 需要 $f(i-1, j+1), f(i,j)$ . 而计算完 $f(i,j)$ 后的 $f(i-1,j)$ 不需要了, 可以将其替换.

即使用一格存储上下两格的结果, 又因为解决步骤数取决于长度短的一边, 所以数组长度为两者间较小的那个.

实际上一维数组就是在模拟, 二维数组的计算流程:

从左到右计算, 每次计算需要上一行的值, 计算后直接用新值替换, 避免空间浪费
从上到下计算新的行时, 更新行首值(此处二维数组已经在初始化里做过了), 然后从左到右

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    // 边界
    if m+n != len(s3) {
        return false
    }

    // 缓存长度取较小值 
    if m < n {
        return isInterleave(s2, s1, s3)
    }

    // 缓存 
    dp := make([]bool, n+1)
    dp[0] = true

    // 最小问题, 初始值
    for i := 1; i < n+1; i++ {
        dp[i] = s2[:i] == s3[:i]
    }

    // 计算
    for i, c1 := range s1 {
        // 对应二维数组的 dp[i][0]
        // 相当于二维数组计算到新的一行
        dp[0] = dp[0] && (c1 == rune(s3[i]))
        for j, c2 := range s2 {
            c3 := rune(s3[i+j+1])
            // 从左到右
            // dp[j+1]: dp[i][j+1]
            // dp[j]: dp[i+1][j] 
            dp[j+1] = (c1 == c3 && dp[j+1]) || (c2 == c3 && dp[j]) 
        } 
    }

    return dp[n]
}

14.3.3 问题97: 子序列的数目

LCR 097. 不同的子序列open in new window

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag
提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

14.3.3.1 分析&题解

解析问题步骤, 每次从S中取出字符和T中字符匹配, 每次面临多个选择, 若需要全部匹配结果可以使用回溯法.

计算解的数目可以使用动态规划.

状态转移方程

输入有两个字符串, 那么方程有两个参数. 假设 $f(i,j)$ 表示S[0,i]中等于T[0,j]的子串数目, 那么最终解就是 $f(m-1,n-1)$ , m,n 为S, T 长度

S短于T, 则不可能有解, 即数目为 0
若S[i]等于T[j], 有两个选择:
- 选择S[i], $f(i,j)=f(i-1,j-1)$
- 舍去S[i], $f(i,j)=f(i-1,j)$
此时, $f(i,j)=f(i-1, j-1)+f(i-1,j)$
若S[i]不等于T[j], 只能舍去S[i], $f(i,j)=f(i-1,j)$

初始值(最小问题解):

$f(-1,-1)$ : 表示S,T均为空, 值为 1
$f(-1, j)$ : S 为空, 不可能有解, 值为 0
$f(i, -1)$ : T为空, 只能有一个解, 值为 1

用二维数组简单表示

S\T	-1	0	n
-1	1	0	0
0	1
...
m	1

然后根据状态方程来填充表格.

迭代+二维数组

计算结果之和上一行和前一行有关可以直接使用两行即可. 列数选择较小的, 因为S一定比T长, 所以就是T的长度

func numDistinct(s string, t string) int {
    m, n := len(s), len(t)
    if m < n {
        return 0
    }
    
    // 缓存
    dp := make([]int, n+1)
    // 初始值
    dp[0] = 1

    // 计算
    for _, cs := range s {
        // 新一行的计算
        prev := dp[0]
        for j, ct := range t {
            cur := 0
            if cs == ct {
                cur = prev + dp[j+1]
            } else {
                cur = dp[j+1]
            }

            // 缓存计算前的值, 下次计算还要用到
            // 缓存的上一行的值: dp[i][j+1]
            prev = dp[j+1]
            // 保存计算结果
            dp[j+1] = cur
        }
    } 

    return dp[n]
}

prev缓存 $f(i-1, j-1)$ , 需要缓存
dp[j]: 代表 $f(i,j-1)$ , 前一个
dp[j+1]: 代表 $f(i-1,j)$ 上一行

Reference

剑指Offer（专项突破版）open in new window

昵称

邮箱

网址

按正序
按倒序
按热度

14.3 双序列问题

# 14.3.1 问题95: 最长公共子序列

# 14.3.1.1 分析&题解

# 状态转移方程

# 迭代 二维数组 SC: O(mn)

# 迭代 SC: O(min(m,n)) 二维数组只保留两行

# 迭代 一维数组

# 14.3.2 问题96: 字符串交织

# 14.3.2.1 分析&题解

# 状态转移方程

# 迭代+二维数组

# 迭代+一维数组

# 14.3.3 问题97: 子序列的数目

# 14.3.3.1 分析&题解

# 状态转移方程

# 迭代+二维数组

# Reference

预览:

14.3.1 问题95: 最长公共子序列

14.3.1.1 分析&题解

状态转移方程

迭代二维数组 SC: O(mn)

迭代 SC: O(min(m,n)) 二维数组只保留两行

迭代一维数组

14.3.2 问题96: 字符串交织

14.3.2.1 分析&题解

状态转移方程

迭代+二维数组

迭代+一维数组

14.3.3 问题97: 子序列的数目

14.3.3.1 分析&题解

状态转移方程

迭代+二维数组

Reference