欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指offer】_17正则表达式的匹配

程序员文章站 2022-07-15 08:26:12
...

题目描述

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

解题思路

就是分两种情况,看表达式的下一个字符是不是'*'

  1. pattern下一个字符不为‘*’:这种情况比较简单,直接匹配当前字符。如果
    匹配成功,继续匹配下一个;如果匹配失败,直接返回false。注意这里的
    “匹配成功”,除了两个字符相同的情况外,还有一种情况,就是pattern的
    当前字符为‘.’,同时str的当前字符不为‘\0’。
  2. pattern下一个字符为‘*’时,稍微复杂一些,因为‘*’可以代表0个或多个。
    这里把这些情况都考虑到:
    • ‘*’匹配0个字符时,str当前字符不变,pattern当前字符后移两位,
      跳过这个‘*’符号;
    • ‘*’匹配1个或多个时,str当前字符移向下一个,pattern当前字符
      不变。(这里匹配1个或多个可以看成一种情况,因为:当匹配一个时,
      由于str移到了下一个字符,而pattern字符不变,就回到了上边的情况a;
      当匹配多于一个字符时,相当于从str的下一个字符继续开始匹配)

代码实现

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(*str == '\0'&& *pattern == '\0')
            return true;
        if(*str != '\0' && *pattern == '\0')
            return false;
        
        //如果表达式的下一个字符不是*
        //正常处理
        //判断当前是否相等或者只要表达式为.并且匹配的字符串不为空
        //然后返回str+,pattern+1判断下一个
        if(*(pattern+1) != '*'){
            if(*str == *pattern || *str != '\0'&& *pattern == '.')
                return match(str+1,pattern+1);
            else
                return false;
        }
        //否则下一个字符为'*'
        else{
            if(*str == *pattern || *str!= '\0' && *pattern == '.')
                return match(str,pattern+2)|| match(str+1,pattern);
            else
                return match(str,pattern+2);
        }
           
    }
};
相关标签: 一些题