本次题目

• 392 判断子序列
• 115 不同的子序列
• 583 两个字符串的删除操作
• 72 编辑距离

392 判断子序列

• DP：
  1. 定义dp数组dp[i][j]表示下标i-1（包括i-1）之前的字符串s和下标j-1（包括j-1）之前的字符串t，相同的子序列长度为dp[i][j]；
  2. 递推公式如果s[i - 1] == t[j - 1]，则dp[i][j] = dp[i - 1][j - 1] + 1，否则dp[i][j] = dp[i][j - 1]；
  3. 初始化dp[0][j]和dp[i][0]为0；
  4. 遍历顺序正序；
  5. 举例。

class Solution {
    public boolean isSubsequence(String s, String t) {
        //DP
        int s_leng = s.length();
        int t_leng = t.length();
        //判断特殊情况
        // if(s_leng == 0) return true;
        // if(s_leng != 0 && t_leng == 0) return false;
        // if(s_leng > t_leng) return false;
        //定义dp数组dp[i][j]表示下标i-1（包括i-1）之前的字符串s
        //和下标j-1（包括j-1）之前的字符串t，相同的子序列长度为dp[i][j]
        int[][] dp = new int[s_leng + 1][t_leng + 1];
        //初始化dp[0][j]和dp[i][0]为0
        //遍历顺序正序
        for(int i = 1; i <= s_leng; i++){
            for(int j = 1; j <= t_leng; j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = dp[i][j - 1];
                }
                // if(dp[i][j] == s_leng) return true;
            }
        }
        if(dp[s_leng][t_leng] == s_leng) return true;
        //最后返回false
        return false;
    }
}
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

115 不同的子序列

• DP：
  1. 定义dp数组dp[i][j]表示下标i-1（包括i-1）之前的s子序列中出现下标j-1之前的t子序列的个数为dp[i][j]；
  2. 递推公式如果s[i - 1] == t[j - 1]，则dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，否则dp[i][j] = dp[i - 1][j]；
  3. 初始化dp[i][0] = 1，dp[0][j] = 0，dp[0][0] = 1；
  4. 遍历顺序正序；
  5. 举例。

class Solution {
    public int numDistinct(String s, String t) {
        //DP
        int s_leng = s.length();
        int t_leng = t.length();
        //判断特殊情况
        if(t_leng == 0) return 1;
        if(s_leng == 0) return 0;
        //定义dp数组dp[i][j]表示下标i-1（包括i-1）之前的s子序列中
        //出现下标j-1之前的t子序列的个数为dp[i][j]
        int[][] dp = new int[s_leng + 1][t_leng + 1];
        //初始化dp[i][0] = 1，dp[0][j] = 0，dp[0][0] = 1
        for(int i = 0; i <= s_leng; i++){
            dp[i][0] = 1;
        }
        //遍历顺序正序
        for(int i = 1; i <= s_leng; i++){
            for(int j = 1; j <= t_leng; j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        //返回结果
        return dp[s_leng][t_leng];
    }
}
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

583 两个字符串的删除操作

• 对比上面115 不同的子序列，本题的两个字符串都可以删除。
• DP：
  1. 定义dp数组dp[i][j]表示下标i-1之前（包括i-1）的子字符串1和下标j-1之前（包括j-1）的子字符串相等时删除的最少次数；
  2. 递推公式如果word1[i - 1] == word2[j - 1]，dp[i][j] = dp[i - 1][j - 1]，否则dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1}；
  3. 初始化dp[i][0] = i和dp[0][j] = j；
  4. 遍历顺序正序；
  5. 举例。

class Solution {
    public int minDistance(String word1, String word2) {
        //DP
        int leng1 = word1.length();
        int leng2 = word2.length();
        //定义dp数组dp[i][j]表示下标i-1之前（包括i-1）的子字符串1
        //和下标j-1之前（包括j-1）的子字符串相等时删除的最少次数
        int[][] dp = new int[leng1 + 1][leng2 + 1];
        //初始化dp[i][0] = i和dp[0][j] = j
        for(int i = 0; i <= leng1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= leng2; j++){
            dp[0][j] = j;
        }
        //遍历顺序正序
        for(int i = 1; i <= leng1; i++){
            for(int j = 1; j <= leng2; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        //返回结果
        return dp[leng1][leng2];
    }
}
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

72 编辑距离

• 对比上题583 两个字符串的删除操作，本题不仅可以删除，还可以插入和替换，但是整体思路一致（插入其中一个字符串就相当于删除另一个字符串）。
• DP：
  1. 定义dp数组dp[i][j]表示下标i-1之前（包括i-1）的字符串1和下标j-1之前（包括j-1）的字符串2的最近编辑距离为dp[i][j]；
  2. 递推公式如果word1[i - 1] == word2[j - 1]，dp[i][j] = dp[i - 1][j - 1]，否则dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1；
  3. 初始化dp[i][0] = i和dp[0][j] = j；
  4. 遍历顺序正序；
  5. 举例。

class Solution {
    public int minDistance(String word1, String word2) {
        //DP
        int leng1 = word1.length();
        int leng2 = word2.length();
        //定义dp数组dp[i][j]表示下标i-1之前（包括i-1）的字符串1
        //和下标j-1之前（包括j-1）的字符串2的最近编辑距离为dp[i][j]
        int[][] dp = new int[leng1 + 1][leng2 + 1];
        //初始化dp[i][0] = i和dp[0][j] = j
        for(int i = 0; i <= leng1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= leng2; j++){
            dp[0][j] = j;
        }
        //遍历顺序正序
        for(int i = 1; i <= leng1; i++){
            for(int j = 1; j <= leng2; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = 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[leng1][leng2];
    }
}
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