Posted 2019-09-14Updated 2021-11-12Leetcode6 minutes read (About 898 words)0 visits

String Matching类型问题总结

这类问题的鼻祖问题Sequence Alignment(Edit distance)在算法课上学习过，但是理解不够深刻，本质上就是二维DP的问题。时间空间复杂度都是O(mn)。
这种String Matching或者DP的问题，一定不要上来就想*号该怎么处理，而是应该用一种recursive的思想去处理（算法的问题就是要把大问题逐渐变成更小的问题）：

对于两个string，想要把两个长string比较的大问题变成两个更短的string比较的问题，那么做法无疑就是比较两个string的最后一位，根据不同的情况可以使他们缩短，然后再比较缩短了的string，再缩短不断重复，这就是recursive的思想。
对于recursive，我们可以发现会有很多的子问题在其中，所以可以用dp[][]数组进行memorize。
进一步总结变成bottom up的DP解法。

Edit Distance：最经典的String matching问题，recursive formula:

*如果a[i]==b[j]*： dp[i][j] = dp[i-1][j-1]
*如果a[i]!=b[i]*：
- dp[i][j] = dp[i-1][j-1]，如果a[i]替换成b[j]
- dp[i][j-1]，如果b[j]被删掉
- dp[j-1][i]，如果a[i]被删掉

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

Regular Expression Matching: recursive formula：

*如果s[i]==p[j]或者p[j]==’.’*：dp[i][j] = dp[i-1][j-1]

*如果p[j]==’*‘*：

如果*代表0个前面字符：dp[i][j] = dp[i][j-2]
如果*代表多个前面字符：只有在pattern中前面的字符与string最后一个字符match(相等或者p是.)的情况下，我们可以直接把string的最后一位消掉，dp[i][j] = dp[i-1][j]

class Solution {
    public boolean isMatch(String s, String p) {
        /**
        if s[i]==p[j]||p[j]=='.' : dp[i][j] = dp[i-1][j-1];
        else if p[j]=='*' : 
            dp[i][j] = dp[i][j-2] (* stands for 0 preceding element) 
                        || (s[i]==p[j-1] || p[i-1]=='.' )&& dp[i-1][j] (* stands for more of preceding element)
        **/
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        //if pattern is empty and string is not, the result must be false, so no need to deal with it.
        
        //deal with the situation that string is empty and pattern is not.
        for(int i = 1;i<=n;i++){
            if(p.charAt(i-1)=='*'){
                dp[0][i] = dp[0][i-2];
            }
        }
        
        for(int i =1;i<=m;i++){
            for(int j =1;j<=n;j++){
                if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p.charAt(j-1)=='*'){
                    dp[i][j] = dp[i][j-2] || ((s.charAt(i-1)==p.charAt(j-2)|| p.charAt(j-2)=='.') && dp[i-1][j]);
                }
                else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}

Wildcard Matching: recursive formula:

*如果s[i]==p[j]或者p[j]==’？’*：dp[i][j] = dp[i-1][j-1]

*如果p[j]==’*‘*：

如果*代表0个字符：dp[i][j] = dp[i][j-1]
如果*代表多个字符：因为*代表多个字符，所以string的最后一位可以直接消掉，dp[i][j] = dp[i-1][j]

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for(int i = 1;i<=n;i++){
            if(p.charAt(i-1)=='*' ){
                dp[0][i] = dp[0][i-1];
            }
        }        
        //对于string不为空，pattern为空的情况，一定是false
        
        for(int i =1;i<=m;i++){
            for(int j =1;j<=n;j++){
                if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='?'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p.charAt(j-1)=='*'){
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }
                else {
                    dp[i][j] = false;
                }
            }
        }
        
        return dp[m][n];
        
    }
}

String Matching类型问题总结

String Matching类型问题总结

Catalogue