剑指 offer刷题

第三章 高质量代码

面试题19 正则表达式匹配

https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c
将str和pattern分为四种情况讨论

• str为空，pattern不为空
• str不为空，pattern为空
• str 和pattern为空
• str和pattern都不为空

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        if(str == null || pattern == null)    return false;
        return matchCore(str,pattern,0,0);
    }
    public boolean matchCore(char[] str,char[] pattern,int strIndex,int patternIndex){
        if(strIndex == str.length && patternIndex == pattern.length)
            return true;
        else if(strIndex != str.length && patternIndex == pattern.length)
            return false;
        else if(strIndex == str.length && patternIndex != pattern.length){
            if(patternIndex +1 < pattern.length && pattern[patternIndex+1] == '*' )
                return matchCore(str,pattern,strIndex,patternIndex+2);
            else
                return false;
        }
        else{
            if(patternIndex+1 < pattern.length && pattern[patternIndex+1] == '*'){
                    //*前面的字符匹配成功
                if( (strIndex <str.length &&pattern[patternIndex] == str[strIndex] )||(pattern[patternIndex]=='.' && strIndex!=str.length )){
                    //匹配，进入下一个状态
                    return matchCore(str,pattern,strIndex+1,patternIndex+2) ||
                    // 匹配成功，继续匹配，即*视为大于1
                        matchCore(str,pattern,strIndex+1,patternIndex)||
                     // 跳过 ，将*视为0
                        matchCore(str,pattern,strIndex,patternIndex+2);
                }else{
                    //*前面的字符没有匹配成功，*视为0次
                    return matchCore(str,pattern,strIndex,patternIndex+2);
                }
            }else{
                if((strIndex < str.length && str[strIndex] == pattern[patternIndex] )|| (pattern[patternIndex] == '.' &&strIndex != str.length))
                   return matchCore(str,pattern,strIndex+1,patternIndex+1);
                else
                    return false;
            }
        }
    }
}