LeetCode.程序员面试金典.1618.Pattern Matching 模式匹配

题目描述

《程序员面试金典（第 6 版）》面试题 16.18. 模式匹配
https://leetcode-cn.com/problems/pattern-matching-lcci/

你有两个字符串，即 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仅包含小写字母。

---

解题过程

首先统计出字符 a,b 在模式中的出现次数，分别为 countA 和 countB
设 lengthA 表示模式 a 在 value 中代表的子串长度，lengthB 表示模式 b 在 value 中代表的子串长度
则有方程 countA * lengthA + countB * lengthB = lengthV ，其中 lengthA 的取值范围是 [0, lengthV / countA]
我们从 0 到 lengthV / countA 依次枚举 lengthA 的值，lengthA 确定后 lengthB 也就确定了。
每次确定一组 lengthA, lengthB 的值后，进行一次匹配，能匹配上则直接返回 true，否则继续枚举下一组 lengthA, lengthB 的值，如果枚举完所有 lengthA 的值都无法匹配，则返回 false

每次匹配的过程如下：
从头开始遍历模式串 pattern，第一次遇到字符 a 时，从 value 串中截取 lengthA 长度的子串作为 a 代表的子串，保存为 aStr，之后在 pattern 中遇到 a 时和 aStr 做比较，不相等则返回 false。遇到字符 b 时同样处理。

private static class SolutionV202006 {
    public boolean patternMatching(String pattern, String value) {
        if (pattern.length() == 0 || value.length() == 0) {
            if (pattern.equals(value)) { // 两个都是空串
                return true;
            }
            if (pattern.length() == 0) { // 模式是空串，value 不是空串
                return false;
            }
            // value 是空串，模式不是空串时，只有当 pattern 是单字符时才能匹配
            return pattern.length() == 1;
        }
        // 字符 a,b 在模式中的出现次数
        int countA = 0, countB = 0;
        for (char c : pattern.toCharArray()) {
            if (c == 'a') {
                countA++;
            } else {
                countB++;
            }
        }
        int lengthV = value.length();
        // a 或 b 的个数是 0 时，只需一次匹配，但当 value 长度无法整除非零个数时直接返回 false
        if (countA == 0) {
            return lengthV % countB == 0 && match(pattern, value, 0, lengthV / countB);
        } else if (countB == 0) {
            return lengthV % countA == 0 && match(pattern, value, lengthV / countA, 0);
        }
        // lengthA 模式 a 在 value 中代表的子串长度， lengthB 模式 b 在 value 中代表的子串长度
        int lengthA = 0, lengthB = 0;
        // 根据方程 countA * lengthA + countB * lengthB = lengthV 枚举 lengthA 的值，lengthA 确定后 lengthB 也就确定了
        for (int i = 0; i <= lengthV / countA; i++) {
            if ((lengthV - countA * i) % countB == 0) {
                lengthA = i;
                lengthB = (lengthV - countA * i) / countB;
                // 进行一次匹配，能匹配上则直接返回 true
                if (match(pattern, value, lengthA, lengthB)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 进行一次匹配
    private boolean match(String pattern, String value, int lengthA, int lengthB) {
        int j = 0;
        String aStr = null, bStr = null;
        for (int i = 0; i < pattern.length(); i++) {
            if (pattern.charAt(i) == 'a') {
                if (null == aStr) {
                    // 第一次先构造 a 代表的子串 aStr
                    aStr = value.substring(j, j + lengthA);
                } else {
                    if (!aStr.equals(value.substring(j, j + lengthA))) {
                        return false;
                    }
                }
                j += lengthA;
            } else {
                if (null == bStr) {
                    // 第一次先构造 b 代表的子串 bStr
                    bStr = value.substring(j, j + lengthB);
                } else {
                    if (!bStr.equals(value.substring(j, j + lengthB))) {
                        return false;
                    }
                }
                j += lengthB;
            }
        }
        return true;
    }
}

---

GitHub代码

algorithms/leetcode/crack/_1618_PatternMatching.java
https://github.com/masikkk/algorithms/blob/master/leetcode/crack/_1618_PatternMatching.java

---