面试题 16.18

​To Index ---
面试题 16.18
难度:Medium
你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
1
```
2
示例 1：
3
​
4
输入： pattern = "abba", value = "dogcatcatdog"
5
输出： true
6
示例 2：
7
​
8
输入： pattern = "abba", value = "dogcatcatfish"
9
输出： false
10
示例 3：
11
​
12
输入： pattern = "aaaa", value = "dogcatcatdog"
13
输出： false
14
示例 4：
15
​
16
输入： pattern = "abba", value = "dogdogdogdog"
17
输出： true
18
解释： "a"="dogdog",b=""，反之也符合规则
19
提示：
20
​
21
0 <= len(pattern) <= 1000
22
0 <= len(value) <= 1000
23
你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。
24
```
Copied!
可以通过一个二元一次方程来逐个判断每个pattern出现的次数，即numAlenA+numBlenB=lenValue;
1
```
2
class Solution {
3
string pattern;
4
inline string patternString(string a, string b)
5
{
6
    string res;
7
    for(auto c: pattern)
8
    {
9
	if(c=='a') res+=a;
10
	else res+=b;
11
    }
12
    return res;
13
}
14
public:
15
bool patternMatching(string pattern, string value) {
16
​
17
    int sizeA=0;
18
    int sizeB=0;
19
​
20
    if(pattern[0]=='b') 
21
    {
22
	string tmp;
23
	for(auto c:pattern)
24
	    tmp+= c=='a' ? 'b' :'a';
25
	this->pattern=tmp;
26
    }
27
    else 
28
	this->pattern=pattern;
29
​
30
    for(auto c:this->pattern)
31
    {
32
	if(c=='a') sizeA++;
33
	else sizeB++;
34
    }
35
​
36
    if(sizeA ==0 && sizeB ==0) return value=="";
37
    if(sizeA==0) 
38
    {
39
	int cntB=value.length()/sizeB;
40
	return patternString("",value.substr(0,cntB)) ==value;
41
    }
42
    if(sizeB==0) 
43
    {
44
	int cntA=value.length()/sizeA;
45
	return patternString(value.substr(0,cntA),"") ==value;
46
    }
47
    int startB=0;
48
    for(auto c:this->pattern)
49
    {
50
	if(c=='a') {
51
	    startB++;
52
	}
53
	else 
54
	    break;
55
    }
56
    //cout<<startB<<endl;
57
    //cout<<sizeA<<endl;
58
    int cntA=value.length()/sizeA;
59
    //     cout<<cntA<<endl;
60
    for(int i=0; i<=cntA;i++)
61
    {
62
	int cntB=(value.length()-sizeA*i)/sizeB;
63
​
64
	string a=value.substr(0,i);
65
	//      cout<<i*startB<<endl;
66
	string b =value.substr(i*startB,cntB);
67
	//       cout<<a<<"  "<<b<<endl;
68
	if(a==b) continue;
69
	//    cout<<patternString(a,b) <<endl;
70
	if(patternString(a,b) == value) return true;
71
​
72
    }
73
    return false;
74
}
75
};
Copied!
1
> 执行用时 :4 ms, 在所有 C++ 提交中击败了63.82%的用户   
2
内存消耗 :10.1 MB, 在所有 C++ 提交中击败了100.00%的用户
Copied!

面试题 16.01

面试题 29

Last modified 5mo ago

Copy link

Contents

面试题 16.18