题解 | #正则表达式匹配#

正则表达式匹配

http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4

动态规划：首先我们定义一个f[i][j]的状态转移方程，其中i 表示str中的第i个字符；j表示pattern中的第j个字符，然后判断是否匹配。我们需要判断两种情况：

第一种是当i、j指向的字符是同一个字母/点号（"."）的时候，我们只需要判断对应位置的字符是否相同，相同则转移状态去判断子问题f[i-1][j-1]是否匹配
然后当 j 为*的时候，可以把 b* 这样的看作一个整体,然后有两种子问题的情况:
1. 第一种是b*匹配完 a 后，继续使用,此时的转移方程就是 f[i-1][j]；
2. 第二种就是b*匹配完a后，就舍弃,此时的转移方程为：f[i][j-2]。
注意：|= “或操作”保证了 f[i-1][j]和f[i][j-2]二者有一个行得通即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        if(!pattern.size())
            return !str.size();
        int f[21][31];
        memset(f, 0, 21* 31 * sizeof(int));
        f[0][0] = 1;
        for(int i = 0; i <= str.size(); i ++){
            for(int j = 0; j <= pattern.size(); j ++){ // i,j均为长度
                if(j > 1 && pattern[j - 1] == '*'){
                    f[i][j] |= f[i][j - 2];
                    if(i > 0 && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.'))
                        f[i][j] |= f[i - 1][j];
                }
                else{
                    if(i > 0 && j > 0 && ((str[i -1] == pattern[j - 1] || pattern[j - 1] == '.')))
                        f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        return f[str.size()][pattern.size()];
    }
};

递归做法：初始考虑将*的重复0次和重复多次分开

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        if(!str.size() && !pattern.size())// "" ""
            return true;
        if(!str.size()){
            if(pattern.size() == 2 && pattern[1] == '*')//"" "a*"
                return true;
            else //"" "a"
                return false;
        }
        if(!pattern.size())// "a" ""
            return false;
        if(str[0] == pattern[0] || pattern[0] == '.'){
            if(pattern.size() > 1 && pattern[1] == '*')
                return match(str, pattern.substr(2)) || match(str.substr(1), pattern);//* 重复0次 或 重复至少1次
            else
                return match(str.substr(1), pattern.substr(1));
        }
        if(str[0] != pattern[0]){
            if(pattern.size() > 1 && pattern[1] == '*')
                return match(str, pattern.substr(2));//* 只能重复0次
            else
                return false;
        }
        return true;
    }
};

简单改进：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        if(!pattern.size())
            return !str.size();
        bool temp = str.size() && (str[0] == pattern[0] || pattern[0] == '.');
        if(pattern.size() > 1 && pattern[1] == '*'){
            return match(str, pattern.substr(2)) || (temp && match(str.substr(1), pattern));
        }
        else
            return temp && match(str.substr(1), pattern.substr(1));
        return true;
    }
};