【算法】【Dynamic Programming】Wildcard Matching

Difficulty:

Hard

Description

Implement wildcard pattern matching with support for

'?'

and

'*'

.

‘?’ Matches any single character.

‘*’ Matches any sequence of characters (including the empty sequence).

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”, “*”) → true

isMatch(“aa”, “a*”) → true

isMatch(“ab”, “?*”) → true

isMatch(“aab”, “c*a*b”) → false

Solution

学习Discuss中最高票回答Linear runtime and constant space solution

再尝试写出代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.length(), plen = p.length();
        int si = , pi = ;  // si和pi分别是s和p的索引
        int ssi = -, ppi;   // ppi记录p中'*'出现的位置
        while (si < slen) {
            // 两个字符匹配（p[pi]==s[si] 或 p[pi]=='?'）
            // 此时s和p的索引都+1（向后移动一个字符）
            if (pi < plen && s[si] == p[pi] || p[pi] == '?') {
                ++si;
                ++pi;
            }

            // p[pi]=='*'，此时要用ppi记录p出现'*'的位置，用ssi记录s可以和'*'匹配的起始位置
            // 个人认为判断有无越界(pi < plen)是必要的
            // 例如，s="abcd", p="*c". 若不判断，则会出现数组越界错误
            else if (pi < plen && p[pi] == '*') {
                ppi = pi++;
                ssi = si;
            }

            // p[pi]和s[si]两个字符都不匹配，但是前面出现了'*'
            else if (ssi != -) {
                pi = ppi + ;
                si = ++ssi;
            }

            // p[pi]和s[si]两个字符都不匹配，前面也没出现'*'
            else return false;
        }

        // s全部匹配完了，现在处理p（可能）余下的部分
        while (pi < plen && p[pi] == '*') ++pi;
        if (pi != plen) return false;
        return true;
    }
};
           

至于为什么这个算法是对的，个人理解如下：

'?'

可以匹配任一字符，这种情况很简单。最主要的问题是

'*'

到底可以匹配多少个字符。

我们这样想，每当在p中遇到一个

'*'

时，就从

'*'

的下一个字符（

'*'

的下一个字符的索引记为ppi）开始与s当前的字符匹配（s当前字符索引用ssi记录），若这两个字符能匹配，p和s的索引都加1；若匹配了k (k≥0) 个字符后，下一个字符匹配不成功，那么

s[ssi]

归为与

'*'

匹配，我们从

s[ssi+1]

和

p[ppi]

开始，继续判断能否匹配。

当p和s能一直这样匹配下去，直到s的末尾（s已经匹配完了），且同时p最后只剩

'*'

或空结尾，那p和s的匹配就成功了。

如果p和s不能匹配，那一定是p中没有

'*'

且有字符与s不匹配，或者是p中有

'*'

，但这个

'*'

一直匹配到s的最后一个字符，且p还多出了除

'*'

外的字符。