字符串匹配

我不是女神ヾ 2023-02-16 13:29 158阅读 0赞

收到一个算法题，把它记录下来  
题目：给你一个字符串s和一个字符规律p，请你来实现一个支持 “.” 和 “\*” 的正则表达式匹配。所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。  
s可能为空，且只包含a-z的小写字母  
p可能为空，且只包含a-z的小写字母,以及字符 “.” 和 “\*”  
"."匹配任意单个字符  
"\*"匹配0-N个前面那个字符  
示例：  
aa a false  
aa a\* true  
ab .\* true  
aab c\*a\*b true  
mississippi mis\*is\*p\*. false

分析：第一个例子，从S首字母开始匹配，比如a和a的匹配，首字母匹配，再分别和后面的字符匹配余下a和空匹配。因为需要整个字符串匹配，此时s不为空，p为空时，不匹配。  
第二个例子里，首字母a和a匹配.因p的第二个字符是 “\*” ,因此下次匹配p还从a\*开始匹配，则是a和a\*的匹配，继续匹配，则是s为空和a\*匹配。 "\*“可以是0。因此s和p匹配。  
第三个例子，a和”.“比较，”.“可以为任何字母，因此匹配，因p的第二位是 “\*”,因此，下一次的匹配是b和 .\* 的匹配。直到s为空，此时p不为空，但p的第二个字符是 “\*” 表示0-N个字符。此时任然匹配  
从上可以分析出，这个题可以用递归实现，当p的头是任意字符+”\*“组合时，下次任然从这个任意字符+”\*"开始匹配。遇到不匹配，就从p+2位继续开始。此时我们要注意aaa和a\*a的匹配。此时匹配s第一个a时，就当作时匹配p第二哥a，这样不影响p的 "\*"可能的总长。

代码如下

bool findString(string s,string p)
    {
        
        if ( 0 == p.size())
        {
        
            return (0 == s.size());
        }
        char first = (0 != s.size()) ? s.at(0) : 0;
        // 第一个字符匹配
        if ((0 != s.size()) && (p.at(0) == first || p.at(0) == '.'))
        {
        
            // p的第二个字符是*，那么下次还从P[0]开始匹配
            if(p.size() > 1 && '*' == p.at(1))
            {
        
                // 遇到a*a第一个匹配，那么删除一个a*后面的a
                if (p.size() > 2 && first == p.at(2))
                {
        
                    p = p.substr(0,2) + p.substr(3);
                }
                return findString(s.substr(1),p);
            }
            else
            {
        
                return findString(s.substr(1),p.substr(1));
            }
        }
        // 就算第一个字符不匹配，但是第一个字符后面有*，那就从p+2开始匹配
        else if (p.at(0) != first && p.size() > 1 && '*' == p.at(1))
        {
        
            return findString(s,p.substr(2));
        }
        return false;
    }