44 Wildcard Matching

44. Wildcard Matching

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

分析& 代码

之前就写过了，但是没有在这写，今天重新写了一遍。

两个指针，一个维持pattern的位置，一个维持str的位置，每一次循环str的idx或者pattern的idx至少有一个会往后移动一步。

当strIdx < srtLen的时候

　　因为存在这个pattern所以要进行尝试，加入匹配0个、1个、2个..试试看能不能匹配到最后，方法是记录上次遇到*的时候的PatternIdx和strIdx，如果后面没有匹配上，那么strIdx就从下一个开始匹配，patternIdx不变。

　　如果没有匹配上，然后又没有上一个*，那么就匹配失败

最后结束了以后，因为到这里的时候str一定已经结束了pattern可能有剩下的*，也要处理掉，最后返回pattenIdx == patternLen，是不是pattern也可以用完

public boolean isMatch(String s, String p) {
    if(s == null || p == null) {
        return false;
    }
    int i = 0;
    int j = 0;
    int sLen = s.length();
    int pLen = p.length();
    int lastPatternIdx = -1;
    int lastStrIdx = -1;
    while(i < s.length()) {
        if(j < pLen && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
            i++;
            j++;
        } else if(j < pLen && p.charAt(j) == '*') {
            lastPatternIdx = j;
            lastStrIdx = i;
            j++;
        } else if(lastPatternIdx != -1) {
            i = ++lastStrIdx;
            j = lastPatternIdx + 1;
        } else {
            return false;
        }
    }
    while(j < pLen && p.charAt(j) == '*') {
        j++;
    }
    return j == pLen;
}

我觉得最差的情况是O(m*n)，比如pattern是“aaaaaaaab”，但是str是“aaaaaaaaaaaaaa”，每次pattern匹配到最后一位都要往前跳