模式匹配 | echo

面试题 16.18. 模式匹配

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1：

1 2	输入： pattern = "abba", value = "dogcatcatdog" 输出： true

示例 2：

1 2	输入： pattern = "abba", value = "dogcatcatfish" 输出： false

示例 3：

1 2	输入： pattern = "aaaa", value = "dogcatcatdog" 输出： false

示例 4：

1
2
3

输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

提示：

0 <= len(pattern) <= 1000
0 <= len(value) <= 1000
你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

我们设 pattern 的长度为 Lp，value 的长度为 Lv。将 a 对应的字符串长度设为 lenA，b 对应的字符串长度设为 lenB。假设 pattern 中出现了 countA 个 a 以及 Lp - countA 个 b ，那么满足下式：
$$
countA * lenA + (Lp - countA) * lenB = Lv
$$
其中 countA 已知，lenA 和 lenB 未知。我们需要求解这个二元一次方程，lenA 和 lenB 必须为自然数，我们可以枚举 lenA （lenA * countA <= Lv）的值，在枚举 lenA 之后，带入等式求解 lenB，如果 lenB 为整数，我们就枚举了一组 a 和 b 的可能长度。

在枚举了长度之后，我们可以根据 pattern 将 value 划分为 Lp 个子串。所有 a 对应的子串必须对应同一个相同的字符串，同样所有 b 对应的子串必须对应同一个字符串，且 a 和 b 对应的字符串必须不一样，不满足这些条件则匹配失败。

在求解二元一次方程时，我们先枚举 lenA，那么必须要求 countA != 0 ，因为在 countA = 0 的情况下，如果原方程有解，那么一定有无数解，这会增加编码的复杂度，因为要处理 countA = 0 这一特殊情况。在统计 a 和 b 出现的次数时，如果出现 countA < countB 的情况，我们将 a 和 b 互相替换，保证 countA > 0。

我们总结判断逻辑：

保证 pattern 中 a 出现的次数不少于 b 出现的次数。如果不满足，我们就将 a 和 b 互换。
如果 value 为空，那么要求 pattern 也为空，或者只出现了 a ，在其他情况下匹配失败。
如果 pattern 为空且 value 不为空，匹配失败。
如果 pattern 和 value 非空，我们就可以枚举 lenA 并判断。

class Solution {
    public boolean patternMatching(String pattern, String value) {
        //计算模式中 'a' 和 'b'数量
        int countA = 0, countB = 0;
        for(char ch : pattern.toCharArray()){
            if(ch == 'a'){
                ++countA;
            }else{
                ++countB;
            }
        }
		// 保证 'a' 出现的次数大于 'b'
        if(countA < countB){
            int temp = countA;
            countA = countB;
            countB = temp;

            char[] array = pattern.toCharArray();
            for(int i = 0; i < array.length; i++){
                array[i] = array[i] == 'a' ? 'b' : 'a';
            }
            pattern = new String(array);
        }
		// 判空处理
        if(value.length() == 0){
            return countB == 0;
        }
        if(pattern.length() == 0){
            return false;
        }
        //枚举lenA
        for(int lenA = 0; countA * lenA <= value.length(); ++lenA){
            //计算 b 对应字符串的总长度
            int rest = value.length() - countA * lenA;
            // countB 为自然数
            if((countB == 0 && rest == 0) || (countB != 0 && rest % countB == 0)){
                int lenB = (countB == 0 ? 0 : rest / countB);
                int pos = 0;
                boolean correct = true;
                String valueA = "", valueB = "";
                for(char ch : pattern.toCharArray()){
                    //判断所有 a 对应的字符串是否相等
                    if(ch == 'a'){
                        String sub = value.substring(pos, pos + lenA);
                        if(valueA.length() == 0){
                            valueA = sub;
                        }else if(! valueA.equals(sub)){
                            correct = false;
                            break;
                        }
                        pos += lenA;
                    }else{
                        //判断所有 b 对应的字符串是否相等
                        String sub = value.substring(pos, pos + lenB);
                        if(valueB.length() == 0){
                            valueB = sub;
                        }else if(! valueB.equals(sub)){
                            correct = false;
                            break;
                        }
                        pos += lenB;
                    }
                }
                // 所有 a 对应的字符串相等，所有 b 对应的字符串相等，
                // a 和 b 对应的字符串不相等，返回true
                if(correct && !valueA.equals(valueB)){
                    return true;
                }
            }
        }
        return false;
    }
}