当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.程序员面试金典.1618.Pattern Matching 模式匹配

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


上一篇 LeetCode.067.Add Binary 二进制求和

下一篇 LeetCode.010.Regular Expression Matching 正则表达式匹配

阅读
评论
881
阅读预计4分钟
创建日期 2020-06-22
修改日期 2020-06-22
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论