面试题 16.18. 模式匹配 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    public boolean patternMatching(String pattern, String value) {
        int countA = 0, countB = 0;
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (c == 'a') {
                countA++;
            } else {
                countB++;
            }
        }

        char[] patternChars = pattern.toCharArray();
        if (countA < countB) {
            int tmp = countA;
            countA = countB;
            countB = tmp;
            for (int i = 0; i < patternChars.length; i++) {
                patternChars[i] = patternChars[i] == 'a' ? 'b' : 'a';
            }
        }

        if (value.length() == 0) {
            // 当 value 为空字符串时，a 或 b 中仅其中一个字符串为空字符串才能匹配，如果 a 和 b 同时存在，因为题意要求 a 和 b 不能相同，那么 b 存在时则无法匹配
            return countB == 0;
        }

        // lengthA * countA + lengthB * countB = value.length()
        for (int lengthA = 0; lengthA * countA <= value.length(); lengthA++) {
            int restLength = value.length() - lengthA * countA;
            // 根据 countB 是否为 0 进行判断
            if ((countB == 0 && restLength == 0) || (countB != 0 && restLength % countB == 0)) {
                int lengthB = countB == 0 ? 0 : restLength / countB;

                String valueA = "", valueB = "";
                int startIndex = 0;
                boolean match = true;
                for (int i = 0; i < patternChars.length; i++) {
                    char p = patternChars[i];
                    if (p == 'a') {
                        String subA = value.substring(startIndex, startIndex + lengthA);
                        if (valueA.equals("")) {
                            valueA = subA;
                        } else if (!valueA.equals(subA)) {
                            match = false;
                            break;
                        }
                        startIndex += lengthA;
                    } else {
                        String subB = value.substring(startIndex, startIndex + lengthB);
                        if (valueB.equals("")) {
                            valueB = subB;
                        } else if (!valueB.equals(subB)) {
                            match = false;
                            break;
                        }
                        startIndex += lengthB;
                    }
                }

                if (match && !valueA.equals(valueB)) {
                    return true;
                }
            }
        }

        return false;
    }
}

References

面试题 16.18. 模式匹配