菜鸟笔记
提升您的技术认知

剑指offer

《剑指Offer》刷题目笔记

剑指Offer 数组

《剑指Offer》二维数组中的查找《剑指Offer》旋转数组的最小数字《剑指Offer》调整数组顺序使奇数位于偶数前面《剑指Offer》数组中出现次数超过一半的数字《剑指Offer》连续子数组的最大和《剑指Offer》把数组排成最小的数《剑指Offer》数组中的逆序对《剑指Offer》数字在排序数组中出现的次数《剑指Offer》数组中只出现一次的数字《剑指Offer》数组中重复的数字《剑指Offer》构建乘积数组

剑指Offer 字符串

《剑指Offer》替换空格《剑指Offer》字符串的排列《剑指Offer》第一个只出现一次的字符《剑指Offer》左旋转字符串《剑指Offer》翻转单词顺序序列《剑指Offer》把字符串转换成整数《剑指Offer》正则表达式匹配《剑指Offer》表示数值的字符串

剑指Offer 链表

《剑指Offer》从尾到头打印链表《剑指Offer》链表中倒数第k个结点《剑指Offer》反转链表《剑指Offer》合并两个排序的链表《剑指Offer》复杂链表的复制《剑指Offer》两个链表的第一个公共结点《剑指Offer》链表中环的入口结点《剑指Offer》删除链表中重复的结点

剑指Offer 树

《剑指Offer》重建二叉树《剑指Offer》树的子结构《剑指Offer》二叉树的镜像《剑指Offer》从上往下打印二叉树《剑指Offer》二叉树中和为某一值的路径《剑指Offer》二叉树的深度《剑指Offer》平衡二叉树《剑指Offer》二叉树的下一个结点《剑指Offer》对称的二叉树《剑指Offer》按之字顺序打印二叉树《剑指Offer》把二叉树打印成多行《剑指Offer》序列化二叉树

《剑指Offer》正则表达式匹配

阅读 : 1017

题目描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符,而''表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"ab*a"均不匹配。

解题思路

这道题有些绕,需要好好思考下。

我们先来分析下如何匹配一个字符,现在只考虑字符'.',不考虑'*'看一下:

如果字符串和模式串的当前字符相等,那么我们继续匹配它们的下一个字符;如果模式串中的字符是'.',那么它可以匹配字符串中的任意字符,我们也可以继续匹配它们的下一个字符。

接下来,把字符'*'考虑进去,它可以匹配任意次的字符,当然出现0次也可以。

我们分两种情况来看:

模式串的下一个字符不是'*',也就是上面说的只有字符'.'的情况。
如果字符串中的第一个字符和模式串中的第一个字符相匹配,那么字符串的模式串都向后移动一个字符,然后匹配剩余的字符串和模式串。如果字符串中的第一个字符和模式中的第一个字符不相匹配,则直接返回false。

模式串的下一个字符是'*',此时就要复杂一些。
因为可能有多种不同的匹配方式。

选择一:无论字符串和模式串当前字符相不相等,我们都将模式串后移两个字符,相当于把模式串中的当前字符和''忽略掉,因为''可以匹配任意次的字符,所以出现0次也可以。

选择二:如果字符串和模式串当前字符相等,则字符串向后移动一个字符。而模式串此时有两个选择:

1、我们可以在模式串向后移动两个字符,继续匹配;

2、也可以保持模式串不变,这样相当于用字符''继续匹配字符串,也就是模式串中的字符''匹配字符串中的字符多个的情况。

用一张图表示如下:

正则表达式匹配

如上图所示,当匹配进入状态2,并且字符串中的字符是'a'时,我们有两个选择:可以进入状态3(在模式串向后移动两个字符),也可以回到状态2(模式串保持不变)。

除此之外,还要注意对空指针的处理。

代码实现(C++)

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        // 指针为空,返回false
        if(str == NULL || pattern == NULL){
            return false;
        }
        return matchCore(str, pattern);
    }
private:
    bool matchCore(char* str, char* pattern){
        // 字符串和模式串都运行到了结尾,返回true
        if(*str == '\0' && *pattern == '\0'){
            return true;
        }
        // 字符串没有到结尾,模式串到了,则返回false
        // 模式串没有到结尾,字符串到了,则根据后续判断进行,需要对'*'做处理
        if((*str != '\0' && *pattern == '\0')){
            return false;
        }
        // 如果模式串的下一个字符是'*',则进入状态机的匹配
        if(*(pattern + 1) == '*'){
            // 如果字符串和模式串相等,或者模式串是'.',并且字符串没有到结尾,则继续匹配
            if(*str == *pattern || (*pattern == '.' && *str != '\0')){
                // 进入下一个状态,就是匹配到了一个
                return matchCore(str + 1, pattern + 2) ||
                    // 保持当前状态,就是继续那这个'*'去匹配
                    matchCore(str + 1, pattern) ||
                    // 跳过这个'*'
                    matchCore(str, pattern + 2);
            }
            // 如果字符串和模式串不相等,则跳过当前模式串的字符和'*',进入新一轮的匹配
            else{
                // 跳过这个'*'
                return matchCore(str, pattern + 2);
            }
        }
        // 如果字符串和模式串相等,或者模式串是'.',并且字符串没有到结尾,则继续匹配
        if(*str == *pattern || (*pattern == '.' && *str != '\0')){
            return matchCore(str + 1, pattern + 1);
        }
        return false;
    }
};