LeetCode: Wildcard Matching 解题报告

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

SOLUTION 1:

DP.

动态规划：输入两个字符串s,p(p包含通配符，用p去匹配s),用flag[i][j]表示字符串p从0到i的的子字符串能否匹配s从0到j的子字符串，我们可以得到如下递推公式：



如果p.charAt(i)==s.charAt(j)或则p.charAt(i)=='?',相当于将最后一个字符匹配掉，所以

flag[i][j]=flag[i-1][j-1];

如果p.charAt(i)=='*'，'*'可以选择匹配0个字符，此时flag[i][j]=flag[i-1][j];可以选择匹配1个字符，此时flag[i][j]=flag[i-1][j-1];……所以，

flag[i][j]=flag[i-1][j]||flag[i-1][j-1]||……||flag[i-1][0]。

但是上面的公式可以化简，当p.charAt(i)=='*'时,有

flag[i][j-1]=flag[i-1][j-1]||flag[i-1][j-2]||……||flag[i-1][0]

所以

flag[i][j]==flag[i-1][j]||flag[i][j-1],所以综合递推公式如下：

                 

空间复杂度？  

由上面的公式可以看出，flag[i][j]只与第i行和第i-1行相关，所以只需要开辟两个一维数组即可。空间复杂度是O(n),时间复杂度是O（mn）。   

public boolean isMatch1(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        
        int lens = s.length();
        int lenp = p.length();
        
        // 创建一个Dp二维数组
        boolean[][] D = new boolean[lens + 1][lenp + 1];
        
        boolean flag = false;
        
        for (int i = 0; i <= lens; i++) {
            flag = false;
            for (int j = 0; j <= lenp; j++) {
                // both is empty.
                if (i == 0 && j == 0) {
                    D[i][j] = true;
                    flag = true;
                    continue;
                }
                
                // if P is empty, s is not empty, it is false.
                if (j == 0) {
                    D[i][j] = false;
                    continue;
                }
                
                // if S is empty, P is not empty
                if (i == 0) {
                    D[i][j] = D[i][j - 1] && p.charAt(j - 1) == '*';
                } else {
                    D[i][j] = (matchChar(s.charAt(i - 1), p.charAt(j - 1)) && D[i - 1][j - 1])
                      || (p.charAt(j - 1) == '*' && (D[i][j - 1] || D[i - 1][j]));    
                }
                
                if (D[i][j]) {
                    flag = true;
                }
                
                // Greedy. 在此即可以退出，因为* 可以匹配余下的所有的字符串。    
                if (D[i][j] && p.charAt(j - 1) == '*' && j == lenp) {
                    return true;
                }
            }
            
            if (!flag) {
                return false;
            }
        }
        
        return D[lens][lenp];
    }
    
    public static boolean matchChar(char c, char p) {
        return (p == '?' || p == c);
    }
}

但是这个算法过不了Leetcode的大数据检查，即使加了几个优化也是如此。

 

SOLUTION 2:

1. 二个指针i, j分别指向字符串、匹配公式。

2. 如果匹配，直接2个指针一起前进。

3. 如果匹配公式是*，在字符串中依次匹配即可。

 下面是迭代程序，要熟悉这个思维：记录上一次开始比较的位置，如图：

 下面程序是直接使用指针记录位置(JAVA中就使用一个index就好了）

    public static boolean matchChar(char c, char p) {
        return (p == '?' || p == c);
    }
    
    public static boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        
        int indexS = 0;
        int indexP = 0;
        
        int lenS = s.length();
        int lenP = p.length();
        
        int preS = 0;
        int preP = 0;
        
        boolean back = false;
        
        while (indexS < lenS) {
            if (indexP < lenP && matchChar(s.charAt(indexS), p.charAt(indexP))) {
                indexS++;
                indexP++;
            } else if (indexP < lenP && p.charAt(indexP) == '*') {
                while (indexP < lenP && p.charAt(indexP) == '*') {
                    indexP++;
                }
                
                //P的最后一个是 *，表示可以匹配任何字符串
                if (indexP == lenP) {
                    return true;
                }
                
                // 记录下这个匹配位置。
                back = true;
                preS = indexS;
                preP = indexP;
            } else if (back) {
                indexS = ++preS;
                indexP = preP;
            } else {
                return false;
            }
        }
        
        // 跳过末尾的所有的*.
        while (indexP < lenP && p.charAt(indexP) == '*') {
            indexP++;
        }
        
        if (indexS == lenS && indexP == lenP) {
            return true;
        }

        return false;
    }

Version 2:

 

public class Solution {
    public boolean isMatch(String s, String p) {
        // 2030.
        if (s == null || p == null) {
            return false;
        }
        
        int indexS = 0;
        int indexP = 0;
        
        int lenS = s.length();
        int lenP = p.length();
        
        int preP = -1;
        int preS = -1;
        
        while (indexS < lenS) {
            if (indexP < lenP && matchChar(p.charAt(indexP), s.charAt(indexS))) {
                indexP++;
                indexS++;
            } else if (indexP < lenP && p.charAt(indexP) == '*') {
                preS = indexS;
                preP = indexP;
                
                // Move to the next character of P.
                indexP++;
            } else if (preP != -1) {
                indexP = preP;
                indexP++;
                
                preS++;
                indexS = preS;
            } else {
                return false;
            }
        }
        
        while (indexP < lenP) {
            if (p.charAt(indexP) != '*') {
                return false;
            }
            indexP++;
        }
        
        return true;
    }
    
    public boolean matchChar(char p, char s) {
        return s == p || p == '?';
    }
}

 

 

 

请移步至主页君GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dp/IsMatch.java

 

九章算法官方解:

http://www.ninechapter.com/solutions/

 

REF:

http://m4tiku.duapp.com/report?pid=123

http://blog.csdn.net/kenden23/article/details/17123497