题目

正则表达式匹配, 判断字符串是否符合给定的正则表达式.

? : 匹配任意单个字符
* : 匹配0个或多个任意字符

Input: "aa", "a"
Output: false
Input: "aa", "*"
Output: true
Input: "cb", "?a"
Output: false
Input: "adceb", "*a*b"
Output: true
Input:  "acdcb", "a*c?b"
Output: false

思路1

分治. 采用递归的形式, 不断缩短字符串的长度. 效率过低.

bool isMatch(string s, string p) {
    if (p.empty()) {
        return s.empty();
    }

    if (s.empty()) {
        for (char c : p) {
            if (c != '*') {
                return false;
            }
        }
        return true;
    }

    if (p[0] == '*') {
        if (p.size() == 1) {
            return true;
        }
        if (p[1] == '*') {
            return isMatch(s, p.substr(1));;
        }
        char x = p[1];
        for (int i = 0;i < s.size(); i++) {
            if (s[i] == x || x == '?') {
                if(isMatch(s.substr(i), p.substr(1)))
                {
                    return true;
                }
            }
        }
    } else if (p[0] == '?') {
        return isMatch(s.substr(1), p.substr(1));
    } else {
        if (p[0] == s[0]) {
            return isMatch(s.substr(1), p.substr(1));
        } else {
            return false;
        }
    }

    return false;
}

思路2

DP. 针对每个字符串的匹配情况, 推算出下一个的字符情况.

bool isMatch(string s, string p) {
    if (p.empty()) return s.empty();
    int m = (int)s.size(), n = (int)p.size();
    bool dp[m+1][n+1];
    memset(dp, 0, (m+1)*(n+1)*sizeof(bool));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        if (p[i-1] == '*') {
            dp[0][i] = dp[0][i-1];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            } else if (p[j-1] == '?' || p[j-1] == s[i-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = false;
            }
        }
    }

    return dp[m][n];
 }

总结

分治很多情况都可以采用DP. 但是DP博大精深, 难以理解, 需要长时间的训练.