每次看到两个字符串的题目时心跳慢半拍，因为这些题目真不是很好写。其中一些题目必须提前想到使用动态规划算法，厘清其中的状态转移方程才能下手。
本文对常见的以双字符串作为输入的算法题目进行分析，试图寻找共同的解题要点。问题包括：
最长公共子序列
最长公共子串
编辑距离
最小覆盖子串
字符串匹配（单模式串）
正则表达式匹配
下面就开始「撸串」~
本文题目难度标识：🟩简单，🟨中等，🟥困难。
两个字符串的相似度（动态规划）
提到两串字符串的「相似度」，我们可以有以下不同定义：
相似度可以指的是两个字符串的公共子串长度。公共子串越长，两串就越相似。
相似度可以指的是一个串转化到另一个串所需要的操作数（编辑距离）。操作数越少，相似度越高。
相似度可以指的是两个字符串的公共子序列的长度。公共子序列越长，相似度越高。
其实上面三种相似度的计算对应了算法中的三个经典问题：最长公共子串、编辑距离、最长公共子序列。其中「最长公共子序列」和「最长公共子串」的缩写均为 LCS。如果在其他地方看到 LCS 时，需结合上下文理解该缩写指代的含义。
在学习动态规划算法时，这些问题你一定逃不掉。看完本章，你能体会到写两个字符串动态规划的状态转移方程时的那种「撸串」的感觉了。
最长公共子序列 Longest Common Subsequence
本小节是第一次引入动态规划算法，接下来将会用保姆级方式（按照《算法导论》中的方式）详细介绍这个问题动态规划方法步骤。更多动态规划算法设计的基础知识的回顾详见 站内文章 动态规划以及题单
给定两个字符串 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}> <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}
动态规划算法设计步骤
动态规划算法的四个步骤：
刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自底向上的方法
利用计算出的信息构造一个最优解
步骤 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}>
如果 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}
如果 xm≠ynx_{m}\ne y_{n} zk≠xmz_{k}\ne x_{m} ZZ Xm−1X_{m-1} YY
如果 xm≠ynx_{m}\ne y_{n} zk≠ynz_{k}\ne y_{n} ZZ XX Yn−1Y_{n-1}
注意，X、Y 序列第一个元素的序号为 1。
步骤 2： 一个递归解
定义 c[i,j]c[i,j] XiX_{i} YjY_{j}
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 的长度
动态规划的两种等价的实现方法
带备忘的自顶向下法
自底向上法（bottom-up method）
列出递归式后，我们发现 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] 为新表 for i=1 to m 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
下面是带备忘版本，运行时间 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)
算法改进：
即使需要重构解也可以去掉表 b。给定 c[i,j]c[i,j] O(1)O(1) [2]
如果不需要重构解，除了去掉 b 以外，可以压缩 c 的空间为一行多一点。[3] 站内文章 动态规划以及题单
最长公共子串 Longest Common Substring
最长公共子串（Longest Common Substring）是指在两个或多个字符串中找出最长的共同连续 子序列。这里的关键词是「连续」，这也是它与最长公共子序列的本质区别。
给定两个字符串 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 分析、拼写检查、语音识别、抄袭侦测和搜索建议。
给你两个单词 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) word1 的长度，n 为 word2 的长度。
空间复杂度 ：O(mn)O(mn) O(mn)O(mn)
最小覆盖子串（滑动窗口）
给你一个字符串 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; 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 ; } }
字符串匹配
单模式串的字符串匹配算法
详看 站内文章 字符串的匹配算法（单模式串）
正则表达式匹配算法（动态规划）
给你一个字符串 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 ; } }
本文参考
《算法导论》习题 15.4-3 ↩︎
《算法导论》习题 15.4-2 ↩︎
《算法导论》习题 15.4-4 ↩︎
