程序员面试金典 – 面试题 16.18. 模式匹配（逻辑题）Michael是个半路程序员-

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; } };