面试题 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仅包含小写字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pattern-matching-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    map <char, int> cnt;

    bool patternMatching(string pattern, string value) {
        //1.pattern 为空
        if (pattern.empty()){
            return value.empty();
        }

        //2.1 pattern非空，value为空。
        //若pattern只由1个字母构成,满足条件,返回true
        if (value.empty()){
            int i = 0;
            while (i < pattern.size() && pattern[i] == pattern[0]){
                i++;
            }
            return i == pattern.size();
        }

        //2.2 pattern非空，value非空
        //统计pattern中a、b的数量
        for (auto ch : pattern){
            cnt[ch]++;
        }

        //若pattern中只有a或者只有b
        if (cnt['a'] == 0) return helper(value, cnt['b']);
        if (cnt['b'] == 0) return helper(value, cnt['a']);

        //假设 a为空 或者 b为空，若符合ok，则返回true
        if (helper(value, cnt['a'])) return true;
        if (helper(value, cnt['b'])) return true;

        //现在a、b都不为空，因为 a*la + b*lb == m，枚举la，计算lb
        int n = value.size();
        for (int la = 1; la * cnt['a'] <= n - cnt['b']; la++){
            if ((n - la * cnt['a']) % cnt['b'] == 0){
                int lb = (n - la * cnt['a']) / cnt['b'];
                if (check(pattern, value, la, lb)){
                    return true;
                }
            }
        }
        return false;
    }

    //只有一个字符的情况，判断value是否能够被k次分割，像aaaa这样的形式
    bool helper(string value, int k){
        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;
    }
    //2个字符都存在的情况，进行检查
    bool check(string pattern, string value, int len_a, int len_b){
        string ps[2] = {"", ""};

        //i是pattern的下标,j是value的下标
        for (int i = 0, j = 0; i < pattern.size(); i++){
            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;
            }
            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 true;
    }
};