原文链接: https://leetcode-cn.com/problems/pattern-matching-lcci

英文原文

You are given two strings, pattern and value. The pattern string consists of just the letters a and b, describing a pattern within a string. For example, the string catcatgocatgo matches the pattern aabab (where cat is a and go is b). It also matches patterns like a, ab, and b. Write a method to determine if value matches pattern. a and b cannot be the same string.

Example 1:

Input:  pattern = "abba", value = "dogcatcatdog"
Output:  true

Example 2:

Input:  pattern = "abba", value = "dogcatcatfish"
Output:  false

Example 3:

Input:  pattern = "aaaa", value = "dogcatcatdog"
Output:  false

Example 4:

Input:  pattern = "abba", value = "dogdogdogdog"
Output:  true
Explanation:  "a"="dogdog",b=""，vice versa.

Note:

• 0 <= len(pattern) <= 1000
• 0 <= len(value) <= 1000
• pattern only contains "a" and "b", value only contains lowercase letters.

中文题目

你有两个字符串，即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=""，反之也符合规则

提示：

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

通过代码

高赞题解

解题思路

代码

class Solution {
public:
    int cnt[2];
    bool patternMatching(string pattern, string value) {
        // 分情况讨论
        // 1. pattern为空
        if (pattern.empty()) return value.empty();
        // 2. pattern不为空
        // 2.1 value为空, 判断pattern是否只由一个字母组成
        if (value.empty()) {
            int i = 0;
            while (i < pattern.size() && pattern[i] == pattern[0]) i ++;
            return i == pattern.size();
        }
        // 2.2 pattern不为空，value不为空
        int n = pattern.size(), m = value.size();
        //   预处理统计a, b字母个数cnt[0], cnt[1]
        cnt[0] = cnt[1] = 0;
        for (auto x: pattern) cnt[x - 'a'] ++;
        //   判断cnt[0], cnt[1]是否有为0的情况
        if (!cnt[0]) return helper(value, cnt[1]);
        else if (!cnt[1]) return helper(value, cnt[0]);

        //  2.2.1 假设使得a,b其中之一为空, 即次数为0
        if (helper(value, cnt[0])) return true;
        if (helper(value, cnt[1])) return true;

        // 2.2.2 a,b都不为空; 枚举a, b匹配的长度，使得a * len_a + b * len_b = m; len_a唯一确定len_b，只需枚举len_a
        for (int len_a = 1; len_a * cnt[0] <= m - cnt[1]; len_a ++) {
            if ((m - len_a * cnt[0]) % cnt[1] != 0) continue;
            int len_b = (m - len_a * cnt[0]) / cnt[1];
            if (check(pattern, value, len_a, len_b)) return true;
        }
        return false;
    }

    bool helper(string value, int k) { // pattern不为空，value不为空. 判断是否可以k次切分value
        int m = value.size();
        if (m % k != 0) return false;
        int len = m / k;
        for (int i = len; i < m; i += len)
            if (value.substr(i, len) != value.substr(0, len)) return false;
        return true;
    }

    bool check(string pattern, string value, int len_a, int len_b) { 
        string ps[2] = {"", ""}; // a, b匹配的字符串
        for (int i = 0, j = 0; i < pattern.size(); i ++) { // i, j指针都是恰当长度的
            if (pattern[i] == 'a') {
                if (ps[0] == "") ps[0] = value.substr(j, len_a);
                else if (value.substr(j, len_a) != ps[0]) return false;
                j += len_a;
            } else if (pattern[i] == 'b') {
                if (ps[1] == "") ps[1] = value.substr(j, len_b);
                else if (value.substr(j, len_b) != ps[1]) return false;
                j += len_b;
            }
        }
        return ps[0] != ps[1]; // a,b所匹配的字符串不能相同（这里之前忘了考虑，多谢@重剑（ Rage Your Dream）指出）
    }
};

统计信息

通过次数	提交次数	AC比率
15428	44897	34.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言