剑指13. 正则表达式

---

匹配标准

image.png image.png image.png

举个例子

image.png image.png image.png

#include <iostream>
#include<stdlib.h>
#include<string.h>
#include<vector>
using namespace std;
class Solution {
    public:
        bool match(char a,char b){
            if (a==b){
                return true;
            }
            else{
                return false;
            }
        }
        bool isMatch(string s, string p) {
            int lens=s.length(),lenp=p.length();
            int i=0,j=0;

            // 将正则表达式细粒度化 aa*->a,a*，存入vector patterns
            vector<string>patterns;
            while(i!=lenp){
                if(p[i+1]=='*'){
                    patterns.push_back(p.substr(i,2));
                    i++;
                }               
                else if(p[i]=='.'){
                    // 可能只有一个.也可能有.*
                    if(p[i+1]=='*'){
                        patterns.push_back(p.substr(i,2));
                        i++;
                    }
                    else{
                        patterns.push_back(".");
                    }
                }
                else{
                    patterns.push_back(p.substr(i,1));
                }
                i++;
            }

            // 横向向是patterns vector，纵向向下是，尝试从上到下从左到右一路走到目的地
            // nil 与空等价
            bool **maps;
            maps=new bool*[s.length()+1];
            for (i=0;i<=s.length();i++){
                maps[i]=new bool[patterns.size()+1];
            }

            for (i=0;i<=s.size();i++){
                for(j=0;j<=patterns.size();j++){
                    maps[i][j]=false;
                }
            }

            // 初始化dp数组，第一列默认为false（除了第一个元素）因为nil空跟任何单元素匹配都是false
            // 第一行如果是从开头就连续的.*、a*这种为true，其他的单元素则为false
            // 第一行与第一列交汇的地方为true
            maps[0][0]=true;
            i=1;

            while(i<=patterns.size()){
                if(patterns[i-1].length()==2){
                    // .* a* 可以与nil匹配，但是.还有其他单元素不行
                    maps[0][i]=true;
                }
                else{
                    break;
                }
                i++;
            }

            for(i=1;i<=s.length();i++){
                for (j=1;j<=patterns.size();j++){
                    // 左上方为true
                    if(maps[i-1][j-1]==true){
                        if(patterns[j-1].length()==1){
                            // a == a
                            if(patterns[j-1]==s.substr(i-1,1)){
                                maps[i][j]=true;
                            }
                            // a == .
                            else if(patterns[j-1]=="."){
                                maps[i][j]=true;
                            }
                        }
                        else if(patterns[j-1].length()==2){
                            // .*
                            if(patterns[j-1].substr(0,1)=="."){
                                maps[i][j]=true;
                            }
                            // a*==a
                            else if(patterns[j-1].substr(0,1)==s.substr(i-1,1)){
                                maps[i][j]=true;
                            }
                        }
                    }
                    // 上侧为true
                    if(maps[i-1][j]==true){
                        // a* == aaa
                        if(patterns[j-1].length()==2&&patterns[j-1].substr(0,1)==s.substr(i-1,1)){
                            maps[i][j]=true;
                        }
                        // .* == a
                        else if(patterns[j-1].length()==2&&patterns[j-1].substr(0,1)=="."){
                            maps[i][j]=true;
                        }
                    }
                    // 左侧为true
                    if(maps[i][j-1]==true){
                        // a* , .*可以为空
                        if(patterns[j-1].length()==2){
                            maps[i][j]=true;
                        }
                    }
                }
            }
            for(i=0;i<=s.length();i++){
                for(j=0;j<=patterns.size();j++){
                    cout<<maps[i][j]<<" ";
                }
                cout<<endl;
            }
            return maps[s.length()][patterns.size()];
        }
};

int main()
{
    Solution *S=new(Solution);
    cout<<S->isMatch("aa",".*...a*");
}