🍊柑橘 RSS 阅读器 - 鸿蒙首款原生 RSS 阅读器

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

本文对常见的以双字符串作为输入的算法题目进行分析，试图寻找共同的解题要点。问题包括：

最长公共子序列
最长公共子串
编辑距离
最小覆盖子串
字符串匹配（单模式串）
正则表达式匹配

下面就开始「撸串」~

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

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

提到两串字符串的「相似度」，我们可以有以下不同定义：

相似度可以指的是两个字符串的公共子串长度。公共子串越长，两串就越相似。
相似度可以指的是一个串转化到另一个串所需要的操作数（编辑距离）。操作数越少，相似度越高。
相似度可以指的是两个字符串的公共子序列的长度。公共子序列越长，相似度越高。

其实上面三种相似度的计算对应了算法中的三个经典问题：最长公共子串、编辑距离、最长公共子序列。其中「最长公共子序列」和「最长公共子串」的缩写均为 LCS。如果在其他地方看到 LCS 时，需结合上下文理解该缩写指代的含义。

在学习动态规划算法时，这些问题你一定逃不掉。看完本章，你能体会到写两个字符串动态规划的状态转移方程时的那种「撸串」的感觉了。

最长公共子序列 Longest Common Subsequence

本小节是第一次引入动态规划算法，接下来将会用保姆级方式（按照《算法导论》中的方式）详细介绍这个问题动态规划方法步骤。更多动态规划算法设计的基础知识的回顾详见站内文章动态规划以及题单。

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

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

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

一些前置定义：

前缀：给定一个序列 $X=<x_{1},x_{2},\dots x_{m}>$ ，对 $i=0,1,\dots,m$ ，定义 $X$ 的第 $i$ 前缀为 $X_{i}= <x_{1},x_{2},\dots,x_{i}>$ 。 $X_{0}$ 表示空串。
子序列：给定一个序列 $X= <x_{1},x_{2},\dots,x_{m}>$ ，另一个序列 $Z= <z_{1},z_{2},\dots,z_{k}>$ 满足以下条件时称为 X 的子序列，即存在一个严格递增的 X 的下标序列 $<i_{1},i_{2},\dots i_{k}>$ ，对所有 $j=1,2,\dots,k$ ，满足 $x_{i_{j}}=z_{j}$ 。
公共子序列：对于序列 X 和 Y，序列 Z 如果既是 X 的子序列又是 Y 的子序列，则 Z 是 X 和 Y 的公共子序列。
最长公共子序列长度： $c[i,j]$ 表示 $X_{i}$ 和 $Y_{j}$ 的 LCS 长度

动态规划算法设计步骤

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

刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自底向上的方法
利用计算出的信息构造一个最优解

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

定理（LCS 最优子结构）：令 $X= <x_{1},x_{2},\dots,x_{m}>$ ， $Y= <y_{1},y_{2},\dots,y_{n}>$ 为两个序列， $Z= <z_{1},z_{2},\dots,z_{k}>$ 为 X 和 Y 的任意 LCS。

如果 $x_{m}=y_{n}$ ，则 $z_{k}=x_{m}=y_{n}$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个 LCS
如果 $x_{m}\ne y_{n}$ ，那么 $z_{k}\ne x_{m}$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个 LCS
如果 $x_{m}\ne y_{n}$ ，那么 $z_{k}\ne y_{n}$ 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的一个 LCS

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

步骤 2：一个递归解

定义 $c[i,j]$ 表示 $X_{i}$ 和 $Y_{j}$ 的 LCS 长度。

$c[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 是为了重构解用的。

自底向上法：

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)$ ^[1]：

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

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)$ ，因为每次递归调用 i 和 j 至少有一个会减少 1。

算法改进：

即使需要重构解也可以去掉表 b。给定 $c[i,j]$ 的值，我们完全可以在 $O(1)$ 时间内判断使用了哪个方向。^[2]
如果不需要重构解，除了去掉 b 以外，可以压缩 c 的空间为一行多一点。^[3] 也就是动态数组的压缩，具体详看站内文章动态规划以及题单。

最长公共子串 Longest Common Substring

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

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

数据范围：公式表示为 $1 \leq |str1|, |str2| \leq 5000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $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

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 所使用的最少操作数。

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

插入一个字符
删除一个字符
替换一个字符

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)$ ，其中 m 为 word1 的长度，n 为 word2 的长度。
空间复杂度： $O(mn)$ ，我们需要大小为 $O(mn)$ 的 D 数组来记录状态值。

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

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

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

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 的，而不是部分字符串。

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

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 章
最长公共子串算法详解：原理与实现 | yzb北
一文详解编辑距离（Levenshtein Distance）-CSDN博客
Levenshtein Distance（编辑距离）算法与使用场景 - throwable - 博客园 (cnblogs.com)

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

本文对常见的以双字符串作为输入的算法题目进行分析，试图寻找共同的解题要点。问题包括：

最长公共子序列
最长公共子串
编辑距离
最小覆盖子串
字符串匹配（单模式串）
正则表达式匹配

下面就开始「撸串」~

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

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

提到两串字符串的「相似度」，我们可以有以下不同定义：

相似度可以指的是两个字符串的公共子串长度。公共子串越长，两串就越相似。
相似度可以指的是一个串转化到另一个串所需要的操作数（编辑距离）。操作数越少，相似度越高。
相似度可以指的是两个字符串的公共子序列的长度。公共子序列越长，相似度越高。

在学习动态规划算法时，这些问题你一定逃不掉。看完本章，你能体会到写两个字符串动态规划的状态转移方程时的那种「撸串」的感觉了。

最长公共子序列 Longest Common Subsequence

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

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

一些前置定义：

前缀：给定一个序列 $X=<x_{1},x_{2},\dots x_{m}>$ ，对 $i=0,1,\dots,m$ ，定义 $X$ 的第 $i$ 前缀为 $X_{i}= <x_{1},x_{2},\dots,x_{i}>$ 。 $X_{0}$ 表示空串。
子序列：给定一个序列 $X= <x_{1},x_{2},\dots,x_{m}>$ ，另一个序列 $Z= <z_{1},z_{2},\dots,z_{k}>$ 满足以下条件时称为 X 的子序列，即存在一个严格递增的 X 的下标序列 $<i_{1},i_{2},\dots i_{k}>$ ，对所有 $j=1,2,\dots,k$ ，满足 $x_{i_{j}}=z_{j}$ 。
公共子序列：对于序列 X 和 Y，序列 Z 如果既是 X 的子序列又是 Y 的子序列，则 Z 是 X 和 Y 的公共子序列。
最长公共子序列长度： $c[i,j]$ 表示 $X_{i}$ 和 $Y_{j}$ 的 LCS 长度

动态规划算法设计步骤

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

刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自底向上的方法
利用计算出的信息构造一个最优解

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

定理（LCS 最优子结构）：令 $X= <x_{1},x_{2},\dots,x_{m}>$ ， $Y= <y_{1},y_{2},\dots,y_{n}>$ 为两个序列， $Z= <z_{1},z_{2},\dots,z_{k}>$ 为 X 和 Y 的任意 LCS。

如果 $x_{m}=y_{n}$ ，则 $z_{k}=x_{m}=y_{n}$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个 LCS
如果 $x_{m}\ne y_{n}$ ，那么 $z_{k}\ne x_{m}$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个 LCS
如果 $x_{m}\ne y_{n}$ ，那么 $z_{k}\ne y_{n}$ 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的一个 LCS

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

步骤 2：一个递归解

定义 $c[i,j]$ 表示 $X_{i}$ 和 $Y_{j}$ 的 LCS 长度。

步骤 3：计算 LCS 的长度

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

带备忘的自顶向下法
自底向上法（bottom-up method）

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

c 表按行主次序计算表项（从左到右，从上到下计算）。算法中表 b 是为了重构解用的。

自底向上法：

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)$ ^[1]：

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

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)$ ，因为每次递归调用 i 和 j 至少有一个会减少 1。

算法改进：

即使需要重构解也可以去掉表 b。给定 $c[i,j]$ 的值，我们完全可以在 $O(1)$ 时间内判断使用了哪个方向。^[2]
如果不需要重构解，除了去掉 b 以外，可以压缩 c 的空间为一行多一点。^[3] 也就是动态数组的压缩，具体详看站内文章动态规划以及题单。

最长公共子串 Longest Common Substring

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

数据范围：公式表示为 $1 \leq |str1|, |str2| \leq 5000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $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

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 指两个字串之间，由一个转换成另一个所需的最少编辑操作次数，允许的编辑操作包括：

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

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

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

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

插入一个字符
删除一个字符
替换一个字符

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)$ ，其中 m 为 word1 的长度，n 为 word2 的长度。
空间复杂度： $O(mn)$ ，我们需要大小为 $O(mn)$ 的 D 数组来记录状态值。

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

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

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

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 的，而不是部分字符串。

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

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 章
最长公共子串算法详解：原理与实现 | yzb北
一文详解编辑距离（Levenshtein Distance）-CSDN博客
Levenshtein Distance（编辑距离）算法与使用场景 - throwable - 博客园 (cnblogs.com)

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

本文对常见的以双字符串作为输入的算法题目进行分析，试图寻找共同的解题要点。问题包括：

最长公共子序列
最长公共子串
编辑距离
最小覆盖子串
字符串匹配（单模式串）
正则表达式匹配

下面就开始「撸串」~

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

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

提到两串字符串的「相似度」，我们可以有以下不同定义：

相似度可以指的是两个字符串的公共子串长度。公共子串越长，两串就越相似。
相似度可以指的是一个串转化到另一个串所需要的操作数（编辑距离）。操作数越少，相似度越高。
相似度可以指的是两个字符串的公共子序列的长度。公共子序列越长，相似度越高。

在学习动态规划算法时，这些问题你一定逃不掉。看完本章，你能体会到写两个字符串动态规划的状态转移方程时的那种「撸串」的感觉了。

最长公共子序列 Longest Common Subsequence

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

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

一些前置定义：

前缀：给定一个序列 $X=<x_{1},x_{2},\dots x_{m}>$ ，对 $i=0,1,\dots,m$ ，定义 $X$ 的第 $i$ 前缀为 $X_{i}= <x_{1},x_{2},\dots,x_{i}>$ 。 $X_{0}$ 表示空串。
子序列：给定一个序列 $X= <x_{1},x_{2},\dots,x_{m}>$ ，另一个序列 $Z= <z_{1},z_{2},\dots,z_{k}>$ 满足以下条件时称为 X 的子序列，即存在一个严格递增的 X 的下标序列 $<i_{1},i_{2},\dots i_{k}>$ ，对所有 $j=1,2,\dots,k$ ，满足 $x_{i_{j}}=z_{j}$ 。
公共子序列：对于序列 X 和 Y，序列 Z 如果既是 X 的子序列又是 Y 的子序列，则 Z 是 X 和 Y 的公共子序列。
最长公共子序列长度： $c[i,j]$ 表示 $X_{i}$ 和 $Y_{j}$ 的 LCS 长度

动态规划算法设计步骤

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

刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自底向上的方法
利用计算出的信息构造一个最优解

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

定理（LCS 最优子结构）：令 $X= <x_{1},x_{2},\dots,x_{m}>$ ， $Y= <y_{1},y_{2},\dots,y_{n}>$ 为两个序列， $Z= <z_{1},z_{2},\dots,z_{k}>$ 为 X 和 Y 的任意 LCS。

如果 $x_{m}=y_{n}$ ，则 $z_{k}=x_{m}=y_{n}$ 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个 LCS
如果 $x_{m}\ne y_{n}$ ，那么 $z_{k}\ne x_{m}$ 意味着 $Z$ 是 $X_{m-1}$ 和 $Y$ 的一个 LCS
如果 $x_{m}\ne y_{n}$ ，那么 $z_{k}\ne y_{n}$ 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$ 的一个 LCS

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

步骤 2：一个递归解

定义 $c[i,j]$ 表示 $X_{i}$ 和 $Y_{j}$ 的 LCS 长度。

步骤 3：计算 LCS 的长度

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

带备忘的自顶向下法
自底向上法（bottom-up method）

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

c 表按行主次序计算表项（从左到右，从上到下计算）。算法中表 b 是为了重构解用的。

自底向上法：

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)$ ^[1]：

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

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)$ ，因为每次递归调用 i 和 j 至少有一个会减少 1。

算法改进：

即使需要重构解也可以去掉表 b。给定 $c[i,j]$ 的值，我们完全可以在 $O(1)$ 时间内判断使用了哪个方向。^[2]
如果不需要重构解，除了去掉 b 以外，可以压缩 c 的空间为一行多一点。^[3] 也就是动态数组的压缩，具体详看站内文章动态规划以及题单。

最长公共子串 Longest Common Substring

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

数据范围：公式表示为 $1 \leq |str1|, |str2| \leq 5000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $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

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 指两个字串之间，由一个转换成另一个所需的最少编辑操作次数，允许的编辑操作包括：

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

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

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

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

插入一个字符
删除一个字符
替换一个字符

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)$ ，其中 m 为 word1 的长度，n 为 word2 的长度。
空间复杂度： $O(mn)$ ，我们需要大小为 $O(mn)$ 的 D 数组来记录状态值。

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

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

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

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 的，而不是部分字符串。

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

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 章
最长公共子串算法详解：原理与实现 | yzb北
一文详解编辑距离（Levenshtein Distance）-CSDN博客
Levenshtein Distance（编辑距离）算法与使用场景 - throwable - 博客园 (cnblogs.com)

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

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

最长公共子序列 Longest Common Subsequence

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

步骤 2： 一个递归解

步骤 3：计算 LCS 的长度

步骤 4：构造 LCS

最长公共子串 Longest Common Substring

编辑距离 Edit Distance

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

字符串匹配

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

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

本文参考

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

最长公共子序列 Longest Common Subsequence

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

步骤 2： 一个递归解

步骤 3：计算 LCS 的长度

步骤 4：构造 LCS

最长公共子串 Longest Common Substring

编辑距离 Edit Distance

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

字符串匹配

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

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

本文参考

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

最长公共子序列 Longest Common Subsequence

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

步骤 2： 一个递归解

步骤 3：计算 LCS 的长度

步骤 4：构造 LCS

最长公共子串 Longest Common Substring

编辑距离 Edit Distance

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

字符串匹配

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

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

本文参考

步骤 2：一个递归解

步骤 2：一个递归解

步骤 2：一个递归解