凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 10. Regular Expression Matching

分类:algorithm| 发布时间:2016-06-30 16:43:00


题目

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

题意

实现支持 '.' 和 '*' 的正则匹配。

解法 1:递归实现

'.' 的匹配比较简单,关键在于 '' 的匹配,出现 '' 时表示它前置的字符可出现任意次。 使用递归可较为直观易懂地解决此问题。

class Solution {
public:
    bool isMatch(string str, string pat) {
        const char *s = str.c_str();
        const char *p = pat.c_str();
        char prece;

        while (*s) {
            if (*(p + 1) == '*') {
                prece = *p;
                ++p;
            }

            if (*p == '*') {
                ++p;
                while (*s) {
                    if (isMatch(s, p)) {
                        return true;
                    }

                    if (*s != prece && prece != '.') {
                        return false;
                    }

                    ++s;
                }
            } else if (*s == *p || *p == '.') {
                ++s;
                ++p;
                if (!*p) {
                    return !*s;
                }
            } else {
                return false;
            }
        }

        while (*p) {
            if (*(p + 1) == '*') {
                p += 2;
            } else {
                break;
            }
        }

        return !*p;
    }
};

当遇到 '*' 时,对比 s 和 p 是否匹配,否则判断 s 是否等于 prece,或者 prece 是否为 '.'。 若相等则对比 s + 1 和 p。

效率有点低,稍等修改下实现:

class Solution {
public:
    bool isMatch(string s, string p) {
        return isMatch(s.c_str(), p.c_str());
    }

    bool isMatch(const char *s, const char *p) {
        char prece;
        while (*s) {
            if (*(p + 1) == '*') {
                prece = *p;
                ++p;
            }

            if (*p == '*') {
                ++p;
                while (*s) {
                    if (isMatch(s, p)) {
                        return true;
                    }

                    if (*s != prece && prece != '.') {
                        return false;
                    }

                    ++s;
                }
            } else if (*s == *p || *p == '.') {
                ++s;
                ++p;

                if (!*p) {
                    return !*s;
                }
            } else {
                return false;
            }
        }

        while (*p) {
            if (*(p + 1) == '*') {
                p += 2;
            } else {
                break;
            }
        }

        return !*p;
    }
};

解法 2:动态规划

class Solution {
public:
    bool isMatch(string s, string p) {
        int sSize = s.size(), pSize = p.size(), i, j;
        bool checked[sSize+1][pSize+1];
        for(j=2, checked[0][0] = true, checked[0][1] = false; j<=pSize; ++j) {
            checked[0][j] = p[j-1] == '*' ? checked[0][j-2] : false;
        }

        for(i = 1; i <= sSize; ++i) {
            for (j = 1, checked[i][0] = false; j <= pSize; ++j) {
                if(p[j-1]=='*') {
                    checked[i][j] = (j>1) && (checked[i][j-2]
                            || ((checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')));
                } else {
                    checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
                }
            }
        }

        return checked[sSize][pSize];
    }
};

用一个 checked 的二维数组记录 s 和 p 的匹配情况。 扫描 p 时分为两种情况(注意在 checked 中的下标表示字符串的长度):

  • 字符为 ’*' 时,checked[i][j] 为真需要满足以下条件
    • j > 1,‘*' 出现在匹配串的开头为非法情况
    • (checked[i][j-2] || ((checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')))
  • 字符不为 ‘*' 时,checked[i][j] 为真需要满足以下条件
    • checked[i - 1][j - 1]为 true
    • (s[i-1] == p[j-1] || p[j-1] == '.'),当前字符匹配,或者遇到了 '.'