[劍指offer] 正規表達式比對

本文首發于我的個人部落格： 尾尾部落

題目描述

請實作一個函數用來比對包括'.'和'*'的正規表達式。模式中的字元'.'表示任意一個字元，而'*'表示它前面的字元可以出現任意次（包含0次）。 在本題中，比對是指字元串的所有字元比對整個模式。例如，字元串"aaa"與模式"a.a"和"ab*ac*a"比對，但是與"aa.a"和"ab*a"均不比對

解題思路

當模式中的第二個字元不是“*”時：

1、如果字元串第一個字元和模式中的第一個字元相比對，那麼字元串和模式都後移一個字元，然後比對剩餘的。

2、如果 字元串第一個字元和模式中的第一個字元相不比對，直接傳回false。

而當模式中的第二個字元是“*”時：

如果字元串第一個字元跟模式第一個字元不比對，則模式後移2個字元，繼續比對。如果字元串第一個字元跟模式第一個字元比對，可以有3種比對方式：

1、模式後移2字元，相當于x*被忽略；

2、字元串後移1字元，模式後移2字元；

3、字元串後移1字元，模式不變，即繼續比對字元下一位，因為*可以比對多位。

參考代碼

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        int sindex = 0, pindex = 0;
        return matchCore(str, sindex, pindex, pattern);
    }
    public boolean matchCore(char[] str, int sindex, int pindex, char[] pattern){
        if(sindex >= str.length && pindex == pattern.length)
            return true;
        if(pindex >= pattern.length && sindex < str.length)
            return false;
        if(pindex+1 < pattern.length && pattern[pindex+1] == '*'){
            if(sindex < str.length && (str[sindex] == pattern[pindex] || pattern[pindex] == '.') ){
                return matchCore(str, sindex, pindex+2, pattern) ||
                    matchCore(str, sindex+1, pindex+2, pattern ) ||
                    matchCore(str, sindex+1, pindex, pattern);
            }else{
                return matchCore(str, sindex, pindex+2, pattern);
            }
        }
        if(sindex < str.length && (str[sindex] == pattern[pindex] || pattern[pindex] == '.'))
            return matchCore(str, sindex+1, pindex+1, pattern);
        return false;
    }
}
           

參考牛客網@披薩大叔