LeetCode 面试题 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 仅包含小写字母。

  点击此处跳转题目。

二、C# 题解

1. 判断长度是否满足要求。
   即判断是否存在一对 (aStr, bStr)，使得 aLen * aNum + bLen * bNum = value.Length。其中

   • aStr / bStr 分别为 a / b 匹配的字符串。
   • aLen / bLen 分别为 aStr / bStr 的长度。
   • aNum / bNum 分别为 pattern 中 a / b 的个数。

2. 对于所有的有序对 (aStr, bStr)，顺序取 pattern 中的每个字符，判断 value 对应位置是否匹配。

  代码中用 lens 存储所有的有序对 (aStr, bStr)。

public class Solution {
    public bool PatternMatching(string pattern, string value) {
        int n    = pattern.Length, l = value.Length;   // pattern 长度
        int aNum = pattern.Sum(a => a == 'a' ? 1 : 0); // pattern 中 a 的个数
        int bNum = n - aNum;                           // pattern 中 b 的个数

        List<int[]> lens = new List<int[]>(); // lens[i][0]/lens[i][1] 分别为 a/b 匹配的字符串长度
        if (aNum == 0) {
            if (l % bNum != 0) return false;
            lens.Add(new[] { 0, l / bNum });
        }
        else if (bNum == 0) {
            if (l % aNum != 0) return false;
            lens.Add(new[] { l / aNum, 0 });
        }
        else
            for (int i = 0; i <= l / aNum; i++)
                if ((l - i * aNum) % bNum == 0)
                    lens.Add(new[] { i, (l - i * aNum) / bNum });

        foreach (var len in lens) {           // 每种 a/b 对应的长度都试一遍
            bool      ans   = true;           // 记录该种长度下是否匹配成功
            string?[] abStr = { null, null }; // 记录 a/b 对应匹配的字符串
            int       index = 0;              // 当前 value 中的匹配位置
            for (int j = 0; j < pattern.Length; j++) {
                int    ab    = pattern[j] - 'a';              // 1 表示 a，2 表示 b
                int    abLen = len[ab];                       // 取出 a_b 对应的匹配字符串长度
                string sub   = value.Substring(index, abLen); // 查看 value 中的字符串
                index += abLen;                               // 更新位置
                if (abStr[ab] == null) {                      // 之前未出现，则用 abStr 记录下来
                    if (abStr[1 - ab] == sub) return false;   // 如果和另一个字符匹配的字符串一样，则返回 false
                    abStr[ab] = sub;
                }
                else if (abStr[ab] != sub) { // 匹配失败
                    ans = false;             // 该情况返回 false
                    break;
                }
            }
            if (ans) return true; // 如果该情况匹配成功，直接返回 true
        }

        return false;
    }
}
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

• 时间：68 ms，击败 66.67% 使用 C# 的用户
• 内存：36.72 MB，击败 33.33% 使用 C# 的用户

---

  优化掉 lens 后，可以提升效率：

public class Solution {
    public bool PatternMatching(string pattern, string value) {
        int n    = pattern.Length, l = value.Length;   // pattern 长度
        int aNum = pattern.Sum(a => a == 'a' ? 1 : 0); // pattern 中 a 的个数
        int bNum = n - aNum;                           // pattern 中 b 的个数

        if (aNum == 0) return Repeat(value, bNum);
        if (bNum == 0) return Repeat(value, aNum);

        for (int aLen = 0; aLen <= l / aNum; aLen++) {
            if ((l - aLen * aNum) % bNum != 0) continue;
            int       bLen  = (l - aLen * aNum) / bNum;
            string?[] abStr = { null, null };
            int       index = 0;
            bool      ans   = true;
            for (var i = 0; i < pattern.Length; i++) {
                int    ab    = pattern[i] - 'a';
                int    abLen = ab == 0 ? aLen : bLen;
                string sub   = value.Substring(index, abLen);
                index += abLen;
                if (abStr[ab] == null) {                    
                    if (abStr[1 - ab] == sub) return false; 
                    abStr[ab] = sub;
                }
                else if (abStr[ab] != sub) { 
                    ans = false;             
                    break;
                }
            }
            if (ans) return true;
        }
        return false;
    }

    // 判断 value 是否重复 n 次
    public bool Repeat(string value, int n) {
        if (value.Length % n != 0) return false;
        int l = value.Length / n;
        for (int i = 0; i < l; i++)
        for (int j = 1; j < n; j++)
            if (value[(j - 1) * l + i] != value[j * l + i])
                return false;

        return true;
    }
}
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

• 时间：60 ms，击败 100.00% 使用 C# 的用户
• 内存：36.51 MB，击败 66.67% 使用 C# 的用户