每日题解:LeetCode 面试题 16.18. 模式匹配
题目描述
你有两个字符串，即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仅包含小写字母。
解法
- whlie循环
class Solution {
public boolean patternMatching(String pattern, String value) {
char[] vArr = value.toCharArray();
if (vArr.length == 0) return pattern.length() < 2;
char[] pArr = pattern.toCharArray();
if (pArr.length == 0) return false;
int x = 0, y = 0;
for (char c : pArr) {
if (c == 'a') x++;
else y++;
}
//只有b或者a的字符串，就是将
if (x == 0) return singleCount(y, value);
if (y == 0) return singleCount(x, value);
//计算a*x+b*y=value.length()
return multiCount(x, y, value, pArr);
}
private boolean multiCount(int aNum, int bNum, String value, char[] pArr) {
int vLen = value.length();
//a字符的最大长度
int aLen = 0, bLen,sumaLen=0;
while (sumaLen<=vLen){
sumaLen=aNum * aLen;
int remain = vLen -sumaLen;
if (remain<0 || remain % bNum != 0) {
aLen++;
continue;
}
bLen = remain / bNum;
String aBase = null, bBase = null, valueStr = "";
int valueIndex = 0;
for (char c : pArr) {
if (c== 'a') {
//这块代码可以提出作为一个公共方法
if (null==aBase) {
aBase = value.substring(valueIndex, valueIndex+ aLen);
}
valueStr+=aBase;
valueIndex+= aLen;
}
if (c == 'b') {
if (null==bBase) {
bBase = value.substring(valueIndex, valueIndex+ bLen);
}
valueStr+=bBase;
valueIndex+= bLen;
}
}
if (aBase != null && bBase != null && aBase.equals(bBase)) return false;
if (valueStr.equals(value))return true;
aLen++;
}
return false;
}
private boolean singleCount(int count, String value) {
int vLen = value.length();
if (vLen % count != 0) return false;
//将字符拆分想等分的判断字符字符是否相等
String base = value.substring(0, vLen / count);
int baseLen = base.length(), index = baseLen;
while (index < vLen) {
String check = value.substring(index, index += baseLen);
if (!base.equals(check)) return false;
}
return true;
}
}
- for循环
class Solution {
public boolean patternMatching(String pattern, String value) {
char[] vArr = value.toCharArray();
if (vArr.length == 0) return pattern.length() < 2;
char[] pArr = pattern.toCharArray();
if (pArr.length == 0) return false;
int x = 0, y = 0;
for (char c : pArr) {
if (c == 'a') x++;
else y++;
}
//只有b或者a的字符串，就是将
if (x == 0) return singleCount(y, value);
if (y == 0) return singleCount(x, value);
//计算a*x+b*y=value.length()
return multiCount(x, y, value, pArr);
}
private boolean multiCount(int aNum, int bNum, String value, char[] pArr) {
int vLen = value.length();
//a字符的最大长度
int aMaxLen = vLen/aNum, bMaxLen = vLen/bNum;
for (int i = 0; i <= aMaxLen;i++){
for (int j = 0;j<= bMaxLen;j++){
int temp = aNum * i + bNum*j;
if(temp==vLen){
int index = 0;
String aBase =null,bBase= null, valueStr = "";
for (char c : pArr) {
if (c == 'a') {
if (null == aBase) aBase = value.substring(index, index + i);
valueStr += aBase;
index += i;
} if (c == 'b') {
if (null == bBase) bBase = value.substring(index, index + j);
valueStr += bBase;
index += j;
}
}
if (aBase != null && bBase != null && aBase.equals(bBase)) return false;
if (valueStr.equals(value)) return true;
}
}
}
return false;
}
private boolean singleCount(int count, String value) {
int vLen = value.length();
if (vLen % count != 0) return false;
String base = value.substring(0, vLen / count);
int baseLen = base.length(), index = baseLen;
while (index < vLen) {
String check = value.substring(index, index += baseLen);
if (!base.equals(check)) return false;
}
return true;
}
}
解题思路
这个题目，边界问题比较难处理，拿出错误的图先祭天再说，这里有两种遍历的思路
这题目可以看成一个解二元一次方程来进行求解
- 已知 a的个数+b的格式=p.length:
aNum+bNum=p.length - a的字符长度 * aNum+b的字符长度 * bNum=value.length :
aLen*aNum+bLen*bNum=value.length
根据以上两个公式，我们进行解答
char[] vArr = value.toCharArray();
//非空判断，由于题目已经告诉我们 pattern,value可能等于0
if (vArr.length == 0) return pattern.length() < 2;
char[] pArr = pattern.toCharArray();
if (pArr.length == 0) return false;
//得到公式一中的aNum,bNum
int x = 0, y = 0;
for (char c : pArr) {
if (c == 'a') x++;
else y++;
}
aNum=0 or bNum=0
当我们提出aNum,bNum后，可能aNum==0ORbNum==0,这种特殊的其情况，我们没必要进行循环了，单独将value均分等长度的字符串，对比字符串就可以了
//单个a或者b长度的字符串的进行判断，均分字符进行处理判断
private boolean singleCount(int count, String value) {
int vLen = value.length();
//不能均分直接返回结果
if (vLen % count != 0) return false;
//将字符拆分相等分的判断字符字符是否相等
String base = value.substring(0, vLen / count);
int baseLen = base.length(), index = baseLen;
while (index < vLen) {
String check = value.substring(index, index += baseLen);
if (!base.equals(check)) return false;
}
return true;
}
aNum!=0 && bNum!=0
这里就需要套用我们的第二个公式，进行遍历计算aLen*aNum+bLen*bNum=value.length
private boolean multiCount(int aNum, int bNum, String value, char[] pArr) {
int vLen = value.length();
int aLen = 0, bLen,sumaLen=0;
while (条件){
遍历过程
}
}
遍历sumaLen表示当前a字符代表字符串的在value字符中的总长度，sumaLen<value.length();，本来循环条件是while (aLen <vLen)，但是出现很多边界问题，后来换了一个条件对比sumaLen，
sumaLen==0,表明value全部使用b字符代表的字符串进行表示，这里可能是均分或者b代表整个字符串sumaLen==value.length();a字符代表整个字符串
计算bLen的长度
sumaLen=aNum * aLen;
//剩余字符长度
int remain = vLen -sumaLen;
if (remain<0 || remain % bNum != 0) {
aLen++;
continue;
}
bLen = remain / bNum;
这里我们需要对剩余字符remain是否<0进行判断，如果aNum><value.length();,会出现剩余字符的长度<0的情况
比如
leetcode万岁！！！！
String aBase = null, bBase = null, valueStr = "";
int valueIndex = 0;
for (char c : pArr) {
if (c== 'a') {
//对字符进行初始化
if (null==aBase) {
aBase = value.substring(valueIndex, valueIndex+ aLen);
}
valueStr+=aBase;
valueIndex+= aLen;
}
if (c == 'b') {
if (null==bBase) {
bBase = value.substring(valueIndex, valueIndex+ bLen);
}
valueStr+=bBase;
valueIndex+= bLen;
}
}
查找a，b所代表的字符串，然后对字符串进行拼接，这里其实可以对每次的字符串进行singleCount的处理，我写法为了偷懒，因为涉及到，当前循环结束，跳入外循环的逻辑，
虽然可以使用标签实现goto跳转到外部循环开始的地方，但是，我觉得可读性低就没写
//题目要求需注意"a"和"b"不能同时表示相同的字符串
if (aBase != null && bBase != null && aBase.equals(bBase)) return false;
if (valueStr.equals(value))return true;
//不满足条件继续往后寻找字符串
aLen++;
以上是whlie循环的写法思路，换成for循环写法，需要考虑两个边界，a字符代表的字符串最长长度是多少，b字符代表的字符串最长长度是多少，
int aMaxLen = vLen/aNum, bMaxLen = vLen/bNum;
以这两个条件作为我们for循环的中止条件
当二元一次方程成立 int temp = aNum * i + bNum*j;，我们就对当前的i,j进行截取字符串，拼接字符串、对比字符串的操作
private boolean multiCount(int aNum, int bNum, String value, char[] pArr) {
int vLen = value.length();
//a字符的最大长度
int aMaxLen = vLen/aNum, bMaxLen = vLen/bNum;
for (int i = 0; i <= aMaxLen;i++){
for (int j = 0;j<= bMaxLen;j++){
int temp = aNum * i + bNum*j;
if(temp==vLen){
int index = 0;
String aBase =null,bBase= null, valueStr = "";
for (char c : pArr) {
if (c == 'a') {
if (null == aBase) aBase = value.substring(index, index + i);
valueStr += aBase;
index += i;
} if (c == 'b') {
if (null == bBase) bBase = value.substring(index, index + j);
valueStr += bBase;
index += j;
}
}
if (aBase != null && bBase != null && aBase.equals(bBase)) return false;
if (valueStr.equals(value)) return true;
}
}
}
return false;
}
优化
其实一开始的时候，我在最后的返回结果都写了 return singleCount(aNum,value) || return singleCount(bNum,value);
当时考虑，会出现a或者b字符代表整个字符串答案，后面想了想其实在遍历的时候，就考虑int aLen = 0, bLen=0两个边界的情况，没必要再次进行判断。