动态规划总结——线性DP（字符串匹配系列）(基于LeetCode题目)_字符串匹配 线性规划

题目汇总

匹配字符串只有仨操作，增删改，这很明显对应三个状态。只要每次选择子串匹配当前子串时最优的操作，即为最终最优的操作了。
dp[i][j] word2在i位置时的子串，由word1，j位置子串变成至少需要多少步。
状态转移方程：
如果i能和j匹配上，很明显直接读上一个word1匹配上一个word2的情况即可。 dp[i][j] = dp[i-1][j-1]
如果匹配不上，我们就有三种操作方式，
1.增，相当于上一个word2的在同样的word1匹配下的情况
dp[i][j] = dp[i-1][j]+1
2.删，相当于上一个word1在同样word2匹配下的情况
dp[i][j] = dp[i][j-1]+1
3.改，相当于上一个word1在上一个word2匹配的情况（同匹配上的情况）
dp[i][j] = dp[i-1][j]+1;
然后求得三者的最小值
min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
初始化，
由于0字符变成一个子串，肯定是一直添加一直爽啊初始化为
dp[0~i][0] = 0~i
一个子串去变成一个空串，全删啦
dp[0][0~j] = 0~j

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];
       
        for (int j = 0; j <= word2.length(); j++){ 
            dp[0][j] = j;
        }

        for (int i = 0; i <= word1.length(); i++){
            dp[i][0] = i;
        }

        for(int i =1;i<=word1.length();i++){
            char c1 = word1.charAt(i-1);
            for(int j=1;j<=word2.length();j++){
                char c2 = word2.charAt(j-1);
                if(c1==c2){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}
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

class Solution {
   public boolean isMatch(String s, String p) {
        int sn = s.length();
        int pn = p.length();
        int i = 0;//s的指针
        int j = 0;//p的指针
        int start = -1;
        int match = 0;
        while (i < sn) {
            if (j < pn && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {//非"*"的写法
                i++;
                j++;
            } else if (j < pn && p.charAt(j) == '*') {//遇到"*"了记录下来
                start = j;
                match = i;
                j++;
            } else if (start != -1) {//匹配不上回退状态
                j = start + 1;//p的指针回退到*之后的元素上
                match++;
                i = match;//i跳过匹配不上的那个字符
            } else {//没有*还匹配不上直接凉凉
                return false;
            }
        }
        while (j < pn) {//清空匹配完成后尾巴多余的*,若不是*则匹配不上
            if (p.charAt(j) != '*') return false;
            j++;
        }
        return true;

    }
    
}
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

俺之前做用的回溯法
字符串匹配常规思路是不是逐一比对嘛，可是这里多了个 * ，该匹配几个字符呢？主要是看后面的串子恰好能匹配的位置。用回溯法的思路的话，就是记录下的位置，如果出现匹配不上了的情况，就用 * 去匹配几个字符去尝试，直到全匹配上（或者确实匹配不上）。
用动规的话，就是用s子串被p子串匹配。当不知道*匹配几个字符时，都试试嘛
dp[i][j] i长度的s子串能否被j长度的p子串匹配
转移方程：
若s[i]= p[j]||p[j] =?,那么就看前一个s子串和p子串的匹配情况。
dp[i][j] = dp[i-1][j-1]
若p[j] = *,如果上一个p子串可以匹配上s子串那也行（第一次匹配字符或者不匹配字符），如果上一个s子串可以被当前p子串匹配也可以(第一次匹配或者多次匹配)
dp[i][j] = dp[i][j-1]||dp[i-1][j];
初始化：
当p为空时，除非s为空要不然百分百匹配不上，如果s为空，p只有为空，或者全是 *，要不然匹配不上。

class Solution {
   public boolean isMatch(String s, String p) {
       boolean[][] dp = new boolean[s.length()+1][p.length()+1];
       dp[0][0] =true;
       for(int i = 0;i<p.length();i++){
           dp[0][i+1] = dp[0][i]&&p.charAt(i)=='*';
       }
       for(int i =1;i<=s.length();i++){
           char sc =  s.charAt(i-1);
           for(int j =1;j<=p.length();j++){
               char pc = p.charAt(j-1);
               if(pc==sc||pc=='?'){
                   dp[i][j] = dp[i-1][j-1];
               }else if(pc=='*'){
                   dp[i][j] = dp[i-1][j]||dp[i][j-1];
               }
           }
       }
        return dp[s.length()][p.length()];
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

可想而知这道题当然是回溯法快一些啊。

这道题与上一题不同的点在于,* 的作用现在匹配任意多前面那个字符。
那么关于*的状态变化就变了，
有两种情况
*前一个字符可以与s串对应位置匹配上，那么就有三种选择，匹配一次，匹配1~n次，匹配0次。
若匹配不上，则只能匹配0次。

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
                return false;
            }
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true;
            for (int i = 0; i < p.length(); i++) { 
                    dp[0][i + 1] = p.charAt(i) == '*' && dp[0][i - 1]; 
            }
            for (int i = 1; i <= s.length(); i++) {
                char sc = s.charAt(i-1);
                for (int j = 1; j <= p.length(); j++) {
                    char pc = p.charAt(j-1);
                    if(pc=='.'||pc==sc){
                        dp[i][j] = dp[i-1][j-1];
                    }else if(pc=='*'){
                        char prec = p.charAt(j-2);
                        if(prec!='.'&&prec!=sc){
                            dp[i][j] = dp[i][j-2];
                        }else{
                            dp[i][j] = dp[i-1][j]||dp[i][j-1]||dp[i][j-2];
                        }
                        
                    }
                }
            }
            return dp[s.length()][p.length()];
        }
    }
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