392. 判断子序列【简单】
题解 暴力双指针很简单，不多说了
class Solution {
public boolean isSubsequence(String s, String t) {
int m=s.length(),n=t.length(),i=0;
for(int j=0;i
if(s.charAt(i)==t.charAt(j))
i++;
}
return i==m;
}
}
时间复杂度： O ( m + n ) O(m+n) O(m+n)
空间复杂度： O ( 1 ) O(1) O(1)
动态规划暴力其实就挺简单的了…而且复杂度也不错，但是官解中还给了动态规划的解法，刚开始不理解，后来看到评论里说的，假如有x条s要处理，此时双指针复杂度为 O ( x ( t l + s l ) ) O(x(tl+sl)) O(x(tl+sl))，但是动态规划复杂度只有 O ( x t l + s l ) O(xtl+sl) O(xtl+sl)，恍然大悟
- 状态定义：dp[i][j] 表示字符串 t 中从位置 i 开始往后26个字母中每个字母第一次出现的位置
- 状态转移方程：如果 t[i] 就是 ‘a’+j，那么 dp[i][j]=i，否则 ‘a’+j 出现在位置 i+1 开始往后，即 dp[i][j]=dp[i+1][j]
（1）t[i]==‘a’+j：dp[i][j] = i
（2）t[i] !=‘a’+j：dp[i][j] = dp[i+1][j] - 遍历顺序：因为遍历到 i 时，i+1必须有值，因此要从后向前遍历；j 从0到25
- 初始条件：dp[tl][i]=tl，表示t中不含该字母
class Solution {
public boolean isSubsequence(String s, String t) {
int sl=s.length(),tl=t.length();
int dp[][]=new int[tl+1][26];
//初始化dp,26个字母在t中的位置设置为tl,表示t中不存在该字母
for(int i=0;i<26;i++)
dp[tl][i]=tl;
//26个字母在t中的位置
for(int i=tl-1;i>=0;i--){
for(int j=0;j<26;j++){
if(t.charAt(i)=='a'+j)
dp[i][j]=i;
else
dp[i][j]=dp[i+1][j];
}
}
int add=0;//t中字符下标
//遍历s中字母i
for(int i=0;i
//t中没有s[i]
if(dp[add][s.charAt(i)-'a']==tl)
return false;
//t挪到t[s[i]]的下一个位置
add=dp[add][s.charAt(i)-'a']+1;
}
return true;
}
}
时间复杂度： O ( 26 ∗ t l + s l ) O(26*tl+sl) O(26∗tl+sl)
空间复杂度： O ( 26 ∗ t l ) O(26*tl) O(26∗tl)
题目272. 编辑距离【困难】
题解又是一道经典的困难题…完全没思路…熟读背诵吧
首先分析操作类型，题目给出了三种：插入、删除和修改，那么对于两个单词A和B来说，一共有六种操作方式，但是会发现三个等式：
- 插入A=删除B（如 A=dog，B=doge）
- 删除A=插入B（如 A=doge，B=dog）
- 修改A=修改B（如 A=cat，B=bat）
所以可将六种操作方式简化为三种，插入A，插入B，修改A
再来看一下如何把问题转化为规模较小的子问题，假设A=horse，B=ros，
- 插入A：假设horse到ro的编辑距离为a，那么horse到ros的编辑距离不超过a+1，因为ro到ros只需要一步插入字符’s’（horse->ro->ros）
- 插入B：假设hors到ros的编辑距离为b，那么horse到ros的编辑距离不超过b+1，因为hors到horse只需要一步插入字符’e’（ros->hors->horse）
- 修改A：假设hors到ros的编辑距离为c，那么horse到ros的编辑距离不超过c+1，因为hors到horse只需要一步插入字符’e’
所以从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1)
最后来讨论一下动态规划的4个重要问题
- 状态定义：dp[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
- 状态转移方程：
其中D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于B[j]，我们在A的末尾添加了一个同样的字符，则D[i][j] 最小可以为 D[i][j-1] + 1；
D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于A[i]，我们在B的末尾添加了一个同样的字符，则D[i][j] 最小可以为 D[i-1][j] + 1；
D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B [j]，我们修改 A [i] 使它们相同，那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j] 最小可以为 D[i-1][j-1]。
借用官解的图举个例子：
- 初始条件：dp[i][0]=i，表示对word1执行 i 次删除操作；dp[0][j]=j，表示对word2执行 j 次删除操作；
- 返回值：dp[n1-1][n2-1]
class Solution {
public int minDistance(String word1, String word2) {
int n1=word1.length(),n2=word2.length();
int dp[][]=new int[n1+1][n2+1];
for(int i=0;i<=n1;i++)
dp[i][0]=i;
for(int j=0;j<=n2;j++)
dp[0][j]=j;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]));
else
dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
}
}
return dp[n1][n2];
}
}
时间复杂度： O ( m n ) O(mn) O(mn)
空间复杂度： O ( m n ) O(mn) O(mn)
p.s 最近涉及字符串的动态规划简直是我的软肋，完全不会做
