模式匹配

发表于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

LeetCode每日一题，面试题16.18.Pattern Matching LCCI

先看题目描述

这也是道和模式匹配相关的问题

算法和思路

这道题想出思路来不难，关键点就在于要想到这道题其实就在于给 a, b 分配合适的长度，将长度分配好以后代入待匹配的字符串中进行匹配，若可以匹配，就返回 true，若遍历了所有的长度可能，均无法匹配，就返回 false，在分配长度时要注意，a 的长度可以决定 b 的长度，故分配长度时遍历一次即可。以 例子 1 为例，pattern 中有 2 个 a，2 个 b，value 的长度为 12，故 a 的可选长度范围为 [0, 6]，遍历[0, 6] 发现 对于每个值均有一个整数值 b 与之对应 ，故 a 长度的可选值列表为 [0, 1, 2, 3, 4, 5, 6]，然后将相应的长度一个个代入看能否有满足题目要求的匹配，发现有就返回 true，没有就返回 false。想到这个思路不难，关键就是实现和一些细节方面的东西，例如边界， pattern 长度和 value 长度为 0 的情况等

算法源码

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
import java.util.LinkedList;
import java.util.List;

class Solution {
    public static boolean patternMatching(String pattern, String value) {
        if (pattern.length() == 0 && value.length() == 0) return true;
        if (pattern.length() == 0) return false;
        int m = 0;
        int n = 0;
        for (char c: pattern.toCharArray()) {
            if (c == 'a') m++;
            else n++;
        }
        if (m * n != 0 && value.length() == 0) return false;
        if (m == 0 || n == 0) {
            int len = Math.max(m, n);
            if (value.length() % len != 0) return false;
            len = value.length() / len;
            String pat = value.substring(0, len);
            for (int i = 0; i < Math.max(m, n); i++) {
                if (!pat.equals(value.substring(len * i, len * (i + 1)))) return false;
            }
            return true;
        }
        List<Integer> vals = new LinkedList<>();
        for (int i = 0; i <= value.length()/m; i++) {
            if ((value.length() - m * i)%n == 0) vals.add(i);
        }
        if (vals.size() == 0) return false;
        for (int val: vals) {
            int val2 = (value.length() - m * val) / n;
            int flag = 0;
            int count = 0;
            String pre_a = null;
            String pre_b = null;
            for (char c : pattern.toCharArray()) {
                if (c == 'a') {
                    String pat1;
                    if (val > 0) pat1 = value.substring(count, count + val);
                    else pat1 = "";
                    if (pre_a != null && !pat1.equals(pre_a)) {
                        flag = 1;
                        break;
                    }
                    pre_a = pat1;
                    count += val;
                } else {
                    String pat2;
                    if (val2 > 0) pat2 = value.substring(count, count + val2);
                    else pat2 = "";
                    if (pre_b != null && !pat2.equals(pre_b)) {
                        flag = 1;
                        break;
                    }
                    pre_b = pat2;
                    count += val2;
                }
            }
            if (flag == 0) return true;
        }
        return false;
    }
}

有一个要注意的点是，比较字符串的值要用 equals() 方法，不能用 ==，因为字符串是引用型数据，== 会比较字符串的地址，equals 才是只比较字符串的值，这个需要注意