每次看到两个字符串的题目时心跳慢半拍，因为这些题目真不是很好写。其中一些题目必须提前想到使用动态规划算法，厘清其中的状态转移方程才能下手。

本文对常见的以双字符串作为输入的算法题目进行分析，试图寻找共同的解题要点。下面就开始「撸串」~

本文题目难度标识：🟩简单，🟨中等，🟥困难。

两个字符串的相似度（动态规划）

两串字符串的相似度如何定义？我们有多重方式：

  1. 相似度指的是公共子串长度。公共子串越长，两串就越相似。
  2. 相似度指的是一个串转化到另一个串所需要的操作数。操作数越少，相似度越高。
  3. 相似度指的是公共子序列的长度。比如现有 S1 和 S2。存在 S3 满足其元素都在 S1 或 S2 出现（不要求连续出现），且在三个串出现顺序相同。S3 越长，相似度越高。

其实上面三种相似度的计算对应了算法中的三个经典问题：最长公共子串、编辑距离、最长公共子序列。其中，「最长公共子序列」和「最长公共子串」的缩写均为 LCS。

当在其他地方看到 LCS 时，需结合上下文理解该缩写指代的含义。

在学习动态规划算法时，LCS 问题是解释动态规划的经典例子，编辑距离问题也可使用动态规划。借助《算法导论》，我们回忆以下动态规划算法设计的基础知识。

动态规划算法设计步骤

动态规划算法的四个步骤：

  1. 刻画一个最优解的结构特征
  2. 递归地定义最优解的值
  3. 计算最优解的值，通常采用自底向上的方法
  4. 利用计算出的信息构造一个最优解
动态规划的实现方法

动态规划的两种等价的实现方法：

  1. 带备忘的自顶向下法（top-down with memoization[^memo]）。按自然的递归形式编写过程，但保存每个子问题的解（数组或散列表），所以称之为带备忘的（memoized）。
  2. 自底向上法（bottom-up method）。恰当定义子问题的「规模」的概念，使得任何子问题都只依赖于「更小的」子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。

两种方法得到的算法具有相同的渐近运行时间，仅有的差异是常量系数不同：

  • 通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法更快。因为自底向上算法没有递归调用的开销，表的维护开销也更小。
  • 如果子问题空间中的某些子问题完全不必求解，自顶向下法的备忘方法更快，因为它只会求解那些绝对必要的子问题。

看完本章，你能体会到写两个字符串动态规划的状态转移方程时的那种「撸串」的感觉了。

img

最长公共子序列 Longest Common Subsequence

🟨 1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列 是这两个字符串所共同拥有的子序列。

一些前置定义：

  • 前缀：给定一个序列 X=<x1,x2,…xm>X=<x_{1},x_{2},\dots x_{m}>，对 i=0,1,…,mi=0,1,\dots,m，定义 XX 的第 ii 前缀为 Xi=<x1,x2,…,xi>X_{i}= <x_{1},x_{2},\dots,x_{i}>。X0X_{0} 表示空串。
  • 子序列：给定一个序列 X=<x1,x2,…,xm>X= <x_{1},x_{2},\dots,x_{m}>，另一个序列 Z=<z1,z2,…,zk>Z= <z_{1},z_{2},\dots,z_{k}> 满足以下条件时称为 X 的子序列，即存在一个严格递增的 X 的下标序列 <i1,i2,…ik><i_{1},i_{2},\dots i_{k}>，对所有 j=1,2,…,kj=1,2,\dots,k，满足 xij=zjx_{i_{j}}=z_{j}。
  • 公共子序列：对于序列 X 和 Y，序列 Z 如果既是 X 的子序列又是 Y 的子序列，则 Z 是 X 和 Y 的公共子序列。
  • 最长公共子序列长度：c[i,j]c[i,j] 表示 XiX_{i} 和 YjY_{j} 的 LCS 长度

本小节是第一次引入动态规划算法，接下来将会用保姆级方式（按照《算法导论》中的方式）详细介绍这个问题动态规划方法步骤。

步骤 1：刻画最长公共子序列的特征

定理（LCS 最优子结构）：令 X=<x1,x2,…,xm>X= <x_{1},x_{2},\dots,x_{m}>，Y=<y1,y2,…,yn>Y= <y_{1},y_{2},\dots,y_{n}> 为两个序列，Z=<z1,z2,…,zk>Z= <z_{1},z_{2},\dots,z_{k}> 为 X 和 Y 的任意 LCS。

  1. 如果 xm=ynx_{m}=y_{n}，则 zk=xm=ynz_{k}=x_{m}=y_{n} 且 Zk−1Z_{k-1} 是 Xm−1X_{m-1} 和 Yn−1Y_{n-1} 的一个 LCS
  2. 如果 xm≠ynx_{m}\ne y_{n}，那么 zk≠xmz_{k}\ne x_{m} 意味着 ZZ 是 Xm−1X_{m-1} 和 YY 的一个 LCS
  3. 如果 xm≠ynx_{m}\ne y_{n}，那么 zk≠ynz_{k}\ne y_{n} 意味着 ZZ 是 XX 和 Yn−1Y_{n-1} 的一个 LCS

注意，X、Y 序列第一个元素的序号为 1。

步骤 2： 一个递归解

定义 c[i,j]c[i,j] 表示 XiX_{i} 和 YjY_{j} 的 LCS 长度。

c[i,j]={0if i=0 or j=0,c[i−1,j−1]+1if i,j>0 and xi=yj,max⁡{c[i,j−1],c[i−1,j]}if i,j>0 and xi≠yjc[i,j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0, \\ c[i-1,j-1] + 1 & \text{if } i,j>0 \text{ and } x_i = y_j, \\ \max\{c[i,j-1], c[i-1,j]\} & \text{if } i,j>0 \text{ and } x_i \neq y_j \end{cases}

步骤 3：计算 LCS 的长度

列出递归式后，我们发现 c[i,j] 总是和左、上或左上有关，这一点启发我们遍历二维数组的顺序。

c 表按行主次序计算表项（从左到右，从上到下计算）。

算法中表 b 是为了重构解用的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LCS-LENGTH(X,Y)
	m=X.length
	n=Y.length
	令 b[1..m,1..n] 和 c[0..m,0..n] 为新表
	// 初始化c表
	for i=1 to m // i 从 1 开始，因为 c[0,0] 的初始化在下一个for循环中
		c[i][0]=0
	for j=0 to n
		c[0][j]=0

	for i=1 to m
		for j=1 to n
			if X[i]==Y[i]
				c[i][j]=c[i-1][j-1]+1 // 两串都吃
				b[i][j]="↖"
			else if c[i-1][j] >= c[i][j-1] // 选大的那串吃
				c[i][j]=c[i-1][j]
				b[i][j]="⬆"
			else
				c[i][j]=c[i][j-1]
				b[i][j]="⬅"
	return c,b

image.png

带备忘版本，运行时间 O(mn)O(mn)[1]：

1
2
3
4
5
6
7
8
MEMOIZED-LCS-LENGTH(X, Y, i, j)
    if c[i, j] > -1
        return c[i, j]
    if i == 0 or j == 0
        return c[i, j] = 0
    if x[i] == y[j]
        return c[i, j] = LCS-LENGTH(X, Y, i - 1, j - 1) + 1
    return c[i, j] = max(LCS-LENGTH(X, Y, i - 1, j), LCS-LENGTH(X, Y, i, j - 1))

步骤 4：构造 LCS

1
2
3
4
5
6
7
8
9
10
PRINT-LCS(b, X, i, j)
	if i==0 or j== 0
		return
	if b[i, j] == "↖"
		PRINT-LCS(b, X, i-1, j-1)
		print x_i
	elseif b[i,j] == "⬆"
		PRINT-LCS(b, X, i-1, j)
	else
		PRINT-LCS(b, X, i, j-1)

运行时间 O(m+n)O(m+n)，因为每次递归调用 i 和 j 至少有一个会减少 1。

算法改进：

  • 即使需要重构解也可以去掉表 b。给定 c[i,j]c[i,j] 的值，我们完全可以在 O(1)O(1) 时间内判断使用了哪个方向。[2]
  • 如果不需要重构解，除了去掉 b 以外，可以压缩 c 的空间为一行多一点。[3]

最长公共子串 Longest Common Substring

最长公共子串（Longest Common Substring）是指在两个或多个字符串中找出最长的共同连续子序列。这里的关键词是「连续」，这也是它与最长公共子序列的本质区别。

🟨 BM66 最长公共子串-牛客网

给定两个字符串 str1 和 str2,输出两个字符串的最长公共子串题目保证 str1 和 str2 的最长公共子串存在且唯一。

数据范围：公式表示为 1≤∣str1∣,∣str2∣≤50001 \leq |str1|, |str2| \leq 5000
要求：空间复杂度 O(n2)O(n^2)，时间复杂度 O(n2)O(n^2) 。

核心思想：

创建一个二维数组 dp[i][j]，表示以字符串 str1 的第 i 个字符和字符串 str2 的第 j 个字符结尾的最长公共子串长度。

  • 当两个字符相匹配时（str1.charAt(i-1)==str2.charAt(j-1)），我们可以基于之前的结果加 1：dp[i][j] = dp[i-1][j-1] + 1
  • 当字符不匹配时，由于子串要求连续，我们需要重置计数：dp[i][j] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        int ans = 0;
        int end = -1;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] +1; // 两串都吃
                }else{
                    dp[i][j] = 0;
                }
                // 记录答案
                if(dp[i][j]>ans){
                    ans = dp[i][j];
                    end = j-1;
                }
            }
        }
        return str2.substring(end+1-ans,end+1);
    }
}

dp 数组可进行空间压缩。详见 站内文章【刷题日记】动态规划题单。

编辑距离 Edit Distance

Levenshtein Distance，一般称为编辑距离（Edit Distance），Levenshtein Distance 只是编辑距离的其中一种）或者莱文斯坦距离，算法概念是俄罗斯科学家弗拉基米尔·莱文斯坦在 1965 年提出。

此算法的概念很简单：Levenshtein Distance 指两个字串之间，由一个转换成另一个所需的最少编辑操作次数，允许的编辑操作包括：

  • 将其中一个字符替换成另一个字符（Substitutions）
  • 插入一个字符（Insertions）
  • 删除一个字符（Deletions）

主要的应用场景有：DNA 分析、拼写检查、语音识别、抄袭侦测和搜索建议。

🟨 72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int minDistance(String word1, String word2) {
        char[] cc1 = word1.toCharArray();
        char[] cc2 = word2.toCharArray();
        int[][] dp = new int[cc1.length+1][cc2.length+1];
        dp[0][0] = 0;
        for(int i=1;i<=cc1.length;i++){
            dp[i][0] = i;
        }
        for(int j=1;j<=cc2.length;j++){
            dp[0][j] = j;
        }
        for(int i=1;i<=cc1.length;i++){
            for(int j=1;j<=cc2.length;j++){
                if(cc1[i-1]==cc2[j-1]){
                    dp[i][j] = dp[i-1][j-1]; // 两串都吃
                }else{
	                // 选一串吃
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+1;
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        return dp[cc1.length][cc2.length];
    }
}

复杂度分析：

  • 时间复杂度 ：O(mn)O(mn)，其中 m 为 word1 的长度，n 为 word2 的长度。
  • 空间复杂度 ：O(mn)O(mn)，我们需要大小为 O(mn)O(mn) 的 D 数组来记录状态值。

最小覆盖子串（滑动窗口）

🟥 76. 最小覆盖子串 - 力扣（LeetCode）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

本题目我认为难点在于「尺蠖」型滑动窗口的构造。一些细节需要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> tmap = new HashMap<>();
        Map<Character,Integer> cnt = new HashMap<>();
        for(char c:t.toCharArray()){
            tmap.merge(c,1,Integer::sum);
        }
        int len = s.length();
        int l=0,r=-1;
        int ansl = -1;
        int ansr = -1;
        int minLen = Integer.MAX_VALUE;
        // 走一步，缩 N 步
        while(r<len){
            r++;
            // 强制走步，不管有效无效
            if(r<len && tmap.containsKey(s.charAt(r))){
                cnt.merge(s.charAt(r),1,Integer::sum);
            }
            // 有效时尝试缩
            while(isValid(cnt,tmap) && l<=r){
		        // 保证在有效状态下更新答案
                if(r-l+1<minLen){
                    ansl=l;
                    ansr=r;
                    minLen = r-l+1;
                }
                cnt.merge(s.charAt(l),-1,Integer::sum);
                l++;
            }
        }
        if(ansl==-1||ansr==-1)return "";
        return s.substring(ansl,ansr+1);
    }
    
    public static boolean isValid(Map<Character,Integer> cnt,Map<Character,Integer> tmap){
        for(Map.Entry<Character,Integer> entry:tmap.entrySet()){
            char k = entry.getKey();
            int v = entry.getValue();
            if(cnt.getOrDefault(k,0)<v){
                return false;
            }
        }
        return true;
    }
}

字符串匹配

单模式串的字符串匹配算法

详看 站内文章字符串的匹配算法（单模式串）。

正则表达式匹配算法（动态规划）

🟥 10. 正则表达式匹配 - 力扣（LeetCode）

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

我认为，本题是「撸串」最复杂的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean isMatch(String s, String p) {
        char[] ccs = s.toCharArray();
        char[] ccp = p.toCharArray();
        
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];

        dp[0][0]=true;
        for(int j=1;j<=p.length();j++){
            if(ccp[j-1]=='*')dp[0][j] = dp[0][j-2];
        }
        for(int i=1;i<=s.length();i++){
            for(int j=1;j<=p.length();j++){
                if(ccp[j-1]=='*'){
                    if(match(ccs[i-1],ccp[j-2])){
	                    // 关键思路：吃掉主串+吃掉主串和模式串+吃掉模式串
                        dp[i][j] = dp[i-1][j] || dp[i-1][j-2] || dp[i][j-2];
                    }else{
	                    // 智能吃掉模式串的 *，看看还有没有机会
                        dp[i][j] = dp[i][j-2]; 
                    }
                }else{
	                // 只能主串和模式串同时被吃掉
                    if(match(ccs[i-1],ccp[j-1])){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
    
    public static boolean match(char a,char b){
        if(a==b||b=='.')return true;
        return false;
    }
}

本文参考

  1. 《算法导论》习题 15.4-3 ↩︎

  2. 《算法导论》习题 15.4-2 ↩︎

  3. 《算法导论》习题 15.4-4 ↩︎