String Matching Problem

Posted on |

Solutions for leetcode 10

Regular Expression Matching

两个字符串匹配的hard题，以前一直觉得很难做，现在感觉就是那么一回事，通过dp来bottom-up的问题很多，这两个就是非常典型的例子，状态转移需要好好研究下不然很容易出错。下次补充dfs + memorized的方法.

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
class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.size();
        int len2 = p.size();
        vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));
        dp[0][0] = true;
        for(int i = 2; i <= len2; ++i){
            if(p[i-1] == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }
        
        for(int i = 1; i <= len1; ++i){
            for(int j = 1; j <= len2; ++j){
                char s_c = s[i-1];
                char p_c = p[j-1];
                if(p_c == '.' || s_c == p_c){
                    dp[i][j] = dp[i-1][j-1];
                }else if(p_c == '*'){
                    if(p[j-2] == '.' || p[j-2] == s_c){
                        dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                    }else{
                        dp[i][j] = dp[i][j-2]; 
                    }
                }
            }
        }
        return dp[len1][len2];
    }
};

wildcard matching

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
class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.size();
        int len2 = p.size();
        vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));
        dp[0][0] = true;
        for(int i = 1; i <= len2; ++i){
            if(p[i-1] == '*'){
                dp[0][i] = dp[0][i-1];
            }else{
                break;
            }
        }
        for(int i = 1; i <= len1; ++i){
            for(int j = 1; j <= len2; ++j){
                char cs = s[i-1];
                char cp = p[j-1];
                if(cp == '?' || cs == cp){
                    dp[i][j] = dp[i-1][j-1];
                }else if( cp == '*'){
                    // match one || no match || match a lot
                    dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
};

One edit distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int sl = s.size();
        int tl = t.size();
        for(int i = 0; i < min(sl,tl);++i){
            if(s[i] != t[i]){
                if(sl == tl){
                    return s.substr(i+1) == t.substr(i+1);
                }else if(sl < tl){
                    return s.substr(i) == t.substr(i+1);
                }else{
                    return s.substr(i+1) == t.substr(i);
                }
            }
        }
        return abs(sl - tl) == 1;
    }
};