gold-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=""，反之也符合规则

提示：

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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean patternMatching(String pattern, String value) {
        if (value == null || value.length() == 0) {
            if (pattern == null || pattern.length() == 0 || pattern.length() == 1) {
                return true;
            } else {
                return false;
            }
        }
        return isMatch(null, null, pattern, value);
    }

    private boolean isMatch(String a, String b, String pattern, String value) {
        if ((pattern == null || pattern.length() == 0) && (value == null || value.length() == 0)) {
            return true;
        }
        if (pattern == null || pattern.length() == 0) {
            return false;
        }
        if (a != null && b != null && a.equals(b)) {
            return false;
        }
        if (a != null && pattern.charAt(0) == 'a' && value.startsWith(a)) {
            return isMatch(a, b, pattern.substring(1), value.substring(a.length()));
        }
        if (b != null && pattern.charAt(0) == 'b' && value.startsWith(b)) {
            return isMatch(a, b, pattern.substring(1), value.substring(b.length()));
        }

        if (a == null && pattern.charAt(0) == 'a') {
            for (int i = 0; i <= value.length(); i++) {
                String aCand = value.substring(0, i);
                boolean res = isMatch(aCand, b, pattern.substring(1), value.substring(i));
                if (res) {
                    return true;
                }
            }
        }
        if (b == null && pattern.charAt(0) == 'b') {
            for (int i = 0; i <= value.length(); i++) {
                String bCand = value.substring(0, i);
                boolean res = isMatch(a, bCand, pattern.substring(1), value.substring(i));
                if (res) {
                    return true;
                }
            }
        }

        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)