程序员面试金典 - 面试题 16.18. 模式匹配(逻辑题)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了程序员面试金典 - 面试题 16.18. 模式匹配(逻辑题),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2457字,纯文字阅读大概需要4分钟。
内容图文
![程序员面试金典 - 面试题 16.18. 模式匹配(逻辑题)](/upload/InfoBanner/zyjiaocheng/635/926665efe843422792c004349eabe3f6.jpg)
1. 题目
你有两个字符串,即pattern和value。
pattern字符串由字母"a"和"b"组成,用于描述字符串中的模式。
例如,字符串"catcatgocatgo"匹配模式"aabab"(其中"cat"是"a",“go"是"b”),该字符串也匹配像"a"、"ab"和"b"这样的模式。
但需注意"a"和"b"不能同时表示相同的字符串。
编写一个方法判断value字符串是否匹配pattern字符串。
示例 1:
输入: pattern = "abba", value = "dogcatcatdog"
输出: true
示例 2:
输入: pattern = "abba", value = "dogcatcatfish"
输出: false
示例 3:
输入: pattern = "aaaa", value = "dogcatcatdog"
输出: false
示例 4:
输入: pattern = "abba", value = "dogdogdogdog"
输出: true
解释: "a"="dogdog",b="",反之也符合规则
提示:
0 <= len(pattern) <= 1000
0 <= len(value) <= 1000
你可以假设pattern只包含字母"a"和"b",value仅包含小写字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/pattern-matching-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 本质:
x*a+y*b=n
的整数解 - 注意例子
"ab", "",结果false
,容易错
class Solution {
public:
bool patternMatching(string pattern, string value) {
if(pattern==value)
return true;
else if(pattern=="" && value!="")
return false;
int i, a = 0, b = 0, vlen = value.size();
for(i = 0; i < pattern.size(); ++i)
{
if(pattern[i]=='a')
a++;
else
b++;
}
if(a==0 || b==0)
{
if(value=="")//只有一种字符,其代表空串即可满足
return true;
a = max(a, b);
return onlyAorB(value, a);
}
//a,b均有的情况
//a,b均可以表示空字符串, "ab",""
if(onlyAorB(value,a) && value.size()!=0)//b表示空串
return true;
if(onlyAorB(value,b) && value.size()!=0)//a表示空串
return true;
//a,b均不表示空
int la=1, lb=1;//a,b代表的长度
while(la*a < vlen)
{
if((vlen-la*a)%b)//不能整除
{
la++;
continue;
}
lb = (vlen-la*a)/b;
if(good(la,lb,pattern,value))
return true;
la++;
}
return false;
}
bool onlyAorB(string& val, int a)
{
if(val.size()%a)//不能整除,不行
return false;
int n = val.size()/a;
string sub = val.substr(0,n);
for(int j = n; j < val.size(); j+=n)
{
if(val.substr(j,n) != sub)
return false;
}
return true;
}
bool good(int la, int lb, string& pat, string& val)
{
int idxa = -1, idxb = -1, i = 0, idx = 0;
while(idxa==-1 || idxb==-1)
{ //找到a,b代表的字符的idx
if(pat[i]=='a')
{
if(idxa == -1)
idxa = idx;
idx += la;
}
else
{
if(idxb == -1)
idxb = idx;
idx += lb;
}
i++;
}
string sa = val.substr(idxa, la);//a代表的字符
string sb = val.substr(idxb, lb);//b代表的字符
int j = 0, delta;
for(i = 0; i < pat.size(); ++i, j+=delta)
{
if(pat[i]=='a')
{
delta = la;
if(val.substr(j,la) != sa)
return false;
}
else
{
delta = lb;
if(val.substr(j,lb) != sb)
return false;
}
}
return true;
}
};
内容总结
以上是互联网集市为您收集整理的程序员面试金典 - 面试题 16.18. 模式匹配(逻辑题)全部内容,希望文章能够帮你解决程序员面试金典 - 面试题 16.18. 模式匹配(逻辑题)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。