面试题 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!
Copy link