字符串 模式匹配

題目

你有兩個(gè)字符串，即pattern和value。 pattern字符串由字母"a"和"b"組成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），該字符串也匹配像"a"、"ab"和"b"這樣的模式。但需注意"a"和"b"不能同時(shí)表示相同的字符串。編寫(xiě)一個(gè)方法判斷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=""，反之也符合規(guī)則

提示：

0 <= len(pattern) <= 1000
0 <= len(value) <= 1000
你可以假設(shè)pattern只包含字母"a"和"b"，value僅包含小寫(xiě)字母。

題解

1. 我們首先保證 pattern\textit{pattern}pattern 中 aaa 出現(xiàn)的次數(shù)不少于 bbb 出現(xiàn)的次數(shù)。如果不滿足，我們就將 aaa 和 bbb 互相替換；
2. 如果 value\textit{value}value 為空，那么要求 pattern\textit{pattern}pattern 也為空（?p=0\ell_p = 0?p?=0）或者只出現(xiàn)了字母 aaa（?p?ca=0\ell_p - c_a = 0?p??ca?=0），這兩種情況均等同于 ?p?ca=0\ell_p - c_a = 0?p??ca?=0。在其余情況下，都無(wú)法匹配成功；
3. 如果 pattern\textit{pattern}pattern 為空且 value\textit{value}value 不為空，那么無(wú)法匹配成功；
4. 如果 pattern\textit{pattern}pattern 和 value\textit{value}value 均非空，我們就可以枚舉 ?a\ell_a?a? 并使用上面提到的算法進(jìn)行判斷。

class Solution {
    public boolean patternMatching(String pattern, String value) {
        int count_a = 0, count_b = 0;
        for (char ch: pattern.toCharArray()) {
            if (ch == 'a') {
                ++count_a;
            } else {
                ++count_b;
            }
        }
        if (count_a < count_b) {
            int temp = count_a;
            count_a = count_b;
            count_b = temp;
            char[] array = pattern.toCharArray();
            for (int i = 0; i < array.length; i++) {
                array[i] = array[i] == 'a' ? 'b' : 'a';
            }
            pattern = new String(array);
        }
        if (value.length() == 0) {
            return count_b == 0;
        }
        if (pattern.length() == 0) {
            return false;
        }
        for (int len_a = 0; count_a * len_a <= value.length(); ++len_a) {
            int rest = value.length() - count_a * len_a;
            if ((count_b == 0 && rest == 0) || (count_b != 0 && rest % count_b == 0)) {
                int len_b = (count_b == 0 ? 0 : rest / count_b);
                int pos = 0;
                boolean correct = true;
                String value_a = "", value_b = "";
                for (char ch: pattern.toCharArray()) {
                    if (ch == 'a') {
                        String sub = value.substring(pos, pos + len_a);
                        if (value_a.length() == 0) {
                            value_a = sub;
                        } else if (!value_a.equals(sub)) {
                            correct = false;
                            break;
                        }
                        pos += len_a;
                    } else {
                        String sub = value.substring(pos, pos + len_b);
                        if (value_b.length() == 0) {
                            value_b = sub;
                        } else if (!value_b.equals(sub)) {
                            correct = false;
                            break;
                        }
                        pos += len_b;
                    }
                }
                if (correct && !value_a.equals(value_b)) {
                    return true;
                }
            }
        }
        return false;
    }
}