算法

(暴力枚举) $O(n^2)$

暴力枚举一下$a$和$b$的长度，$a$的长度范围是$[0, vlen \, / \, \\# \, of \, a \, in \, pattern]$，如果确定了$a$的长度，那么$b$代表的是什么样的字符串也就确定了，即$blen = (vlen - alen \, * \, \\# \, of \, a) / \\# \, of \, b$。其中$\\#$表示数量。当我们每确定一个$a$的长度的时候，那么我们就可以确定当前的$a$在$value$中代表的是怎样的子字符串了，这样我们也可以联锁推出$b$是怎样的子字符串。

Java 代码

class Solution {
    public boolean patternMatching(String pattern, String value) {
        if (pattern.length() == 0) {
            return value.length() == 0;
        }
        int vlen = value.length();
        int plen = pattern.length();
        int[] freq = new int[2];
        for (int i = 0; i < plen; ++i) {
            freq[pattern.charAt(i) - 'a']++;
        }
        int al = freq[0] == 0 ? 0 : vlen / freq[0];
        for (int i = 0; i <= al; ++i) {
            if (freq[1] != 0 && (vlen - i * freq[0]) % freq[1] != 0) {
                continue;
            }
            if (freq[1] == 0 && i * freq[0] < vlen) continue;
            int bl = freq[1] == 0 ? 0 : (vlen - i * freq[0]) / freq[1];
            if (match(pattern, value, i, bl)) {
                return true;
            }
        }
        return false;
    }

    public boolean match(String p, String v, int al, int bl) {
        String ap = null;
        String bp = null;
        int start = 0;
        for (int i = 0; i < p.length(); ++i) {
            char c = p.charAt(i);
            if (c == 'a') {
                if (ap == null) {
                    ap = v.substring(start, start + al);
                }
                else if (!ap.equals(v.substring(start, start + al))) {
                    return false;
                }
                start += al;
            }
            else {
                if (bp == null) {
                    bp = v.substring(start, start + bl);
                }
                else if (!bp.equals(v.substring(start, start + bl))) {
                    return false;
                }
                start += bl;
            }
            if (start > v.length()) {
                return false;
            }
            if (ap != null && bp != null && ap.equals(bp)) {
                return false;
            }
        }
        return true;
    }
}