leetcode 面试题16.18.模式匹配：复现双百算法（分类别讨论），C++带详细注解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:
bool kSegment(string value,int k)//判断value能否被分成k个一样的字串
{
    int len=value.size();//求value长度
    if(len%k!=0) return false;//长度不是k的整数倍，不能
    int m=len/k;//求k等分后每个字符串的长度
    for(int i=m;i<len;i+=m)//看k个字符串是否相等
    {
        if(value.substr(i,m)!=value.substr(0,m)) return false;//出现与第一个字串不等的情况，返回假
    }
    return true;//都等返回真
}

bool check(string pattern,string value,int len_a,int len_b)//pattern，value都不空，给定a，b模式的长度，判断能否匹配
{//pattern 中ab都有，且ab不为空串
    string str[2]={"",""};//存放a，b所代表的串
    for(int i=0,j=0;i<pattern.size();i++)//遍历pattern
    {
        if(pattern[i]=='a')//遇到a
        {
            if(str[0]=="") str[0]=value.substr(j,len_a);//第一次遇到就把此处往后len_a个字符赋给str[0]
            else//不是第一次遇到
            {
                if(value.substr(j,len_a)!=str[0]) return false;//检查此处往后len_a个元素是否和a相同，不同为假
            }
            j+=len_a;//value往后退len_a个元素
            
        }
        if(pattern[i]=='b')//遇到b
        {
            if(str[1]=="") str[1]=value.substr(j,len_b);//第一次遇到就把此处往后len_b个字符赋给str[1]
            else//不是第一次遇到
            {
                if(value.substr(j,len_b)!=str[1]) return false;//检查此处往后len_b个元素是否和b相同，不同为假
            }
            j+=len_b;//value往后退len_a个元素
            
        }
    }
    return str[0]!=str[1];//若a，b不同返回真，相同则不行
}
    int cnt[2]={0};//全局变量，存放pattern中a，b各出现的次数
    bool patternMatching(string pattern, string value) {//分情况讨论
        if(pattern.empty()) return value.empty();//1.pattern空，value空为真否则为假
        if(value.empty())//2.patt不空 2.1若value为空，看pattern是否只有一种字符组成，该字符代表空串
        {
            int len=pattern.size();//长度
            for(int i=1;i<len;i++)//遍历pattern
            {
                if(pattern[i]!=pattern[0]) return false;//不止一种字符组成
            }
            return true;//是只有一种字符
        }
        //2.2pattern value都不空
        for(auto str:pattern) cnt[str-'a']++;//巧妙利用ascII码统计
        //2.2.1判断pattern中是否只有一种字符
        if(cnt[0]==0) return kSegment(value, cnt[1]);//返回value能否被分成cnt[1]个一样的串
        if(cnt[1]==0) return kSegment(value, cnt[0]);//同样
        //2.2.2pattern中a，b都有,看能否把其中一个当作空串,
        if(kSegment(value, cnt[0])) return true;//把b当空串，且value能被分成a的个数个一样的串，则为真
        if(kSegment(value, cnt[1])) return true;//同样
        //2.2.3 pattern中a，b都有且都不为空，value也不空，此时需要讨论a，b代表串的长度
        int m=pattern.size(),n=value.size();//求长度
        for(int len_a=1;len_a*cnt[0]<=n-cnt[1];len_a++)//枚举a长度：最小为1，最大为n-cnt[1]
        {
            if((n-cnt[0]*len_a)%cnt[1]!=0) continue;//b字符串长度不为整数跳过
            int len_b=(n-cnt[0]*len_a)/cnt[1];//b串长度
            if(check(pattern,value,len_a,len_b)) return true;//找到一种符合条件的
        }
        return false;//没有符合条件的
    }
};