Keshawn_lu's Blog

Leetcode 面试题 16.18. 模式匹配

字符串
字数统计: 872阅读时长: 4 min
2020/06/22 Share

题目简介：

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1：

1
2
输入： pattern = "abba", value = "dogcatcatdog"
输出： true

示例 2：

1
2
输入： pattern = "abba", value = "dogcatcatfish"
输出： false

示例 3：

1
2
输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false

示例 4：

1
2
3
输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

提示：

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

思路：

我们可以分为以下几种情况进行讨论：

  1. pattern为空：此时的结果取决于value是否为空
  2. value为空：此时若pattern由一个字符构成，则符合匹配，否则不符合
  3. pattern, value均不为空，统计字符a和字符b的数量：
    1. 若a和b其中有一个数量为0，假设a的数量为0，则能计算出每个单词的长度为value.size() / count_b，然后遍历value，用substr()进行单词分割，若每个单词相同则匹配成功，否则失败。
    2. 两者数量均不为空，则开始枚举单词的长度，首先wordA_len * count_a + wordB_len * count_b = value.size()是固定的，所以我们枚举wordA_len，从0枚举到value.size()，其中边界值均能取到，因为存在a或b代表空字符串的情况。然后就根据pattern中出现的字符来分割单词，并判断相同字符所代表的单词是否相同，从而判断是否能匹配成功。

tip:

  • 注意单词长度枚举时的边界值，0和value.size()均可以取到。
  • 擅长使用substr()函数。
  • 注意check()函数的具体实现代码。

代码如下：

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Solution {
public:
    bool patternMatching(string pattern, string value) {

        int count_a = 0;
        int count_b = 0;

        //pattern为空
        if(pattern.empty())
            return value.empty();

        if(value.empty()){

            //判断pattern是否由一个字符构成
            for(int i = 1; i < pattern.size(); i++){

                if(pattern[i] != pattern[0])
                    return false;
            }
            return true;
        }

        //均不为空的情况
        for(int i = 0; i < pattern.size(); i++){

            if(pattern[i] == 'a')
                count_a++;
            else
                count_b++;
        }
        //有一个为空
        if(count_a == 0){

            if(value.size() % count_b != 0)
                return false;
            int word_len = value.size() / count_b;
            for(int i = word_len; i < value.size(); i += word_len){

                if(value.substr(i, word_len) != value.substr(0, word_len))
                    return false;
            }
            return true;
        }
        if(count_b == 0){

            if(value.size() % count_a != 0)
                return false;
            int word_len = value.size() / count_a;
            for(int i = word_len; i < value.size(); i += word_len){

                if(value.substr(i, word_len) != value.substr(0, word_len))
                    return false;
            }
            return true;
        }

        //开始枚举单词长度,
        //wordA_len * count_a + wordB_len * count_b = value.size()
        for(int wordA_len = 0; wordA_len * count_a <= value.size(); wordA_len++){

            if( (value.size() - wordA_len * count_a) % count_b != 0)
                continue;
            int wordB_len = (value.size() - wordA_len * count_a) / count_b;
            if(check(pattern, value, wordA_len, wordB_len))
                return true;
        }

        return false;
    }

    bool check(string pattern, string value, int wordA_len, int wordB_len){

        string wordA = "";
        string wordB = "";

        for(int i = 0, j = 0; i < pattern.size(); i++){

            if(pattern[i] == 'a'){

                if(wordA == "")
                    wordA = value.substr(j, wordA_len);
                else{
                    if(value.substr(j, wordA_len) != wordA)
                        return false;
                }
                j += wordA_len;
            }
            else if(pattern[i] == 'b'){

                if(wordB == "")
                    wordB = value.substr(j, wordB_len);
                else{
                    if(value.substr(j, wordB_len) != wordB)
                        return false;
                }
                j += wordB_len;
            }
        }
        return true;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网