每日题解: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两个边界的情况，没必要再次进行判断。

清水1024