LeetCode 0290. 单词规律

【LetMeFly】290.单词规律

力扣题目链接：https://leetcode.cn/problems/word-pattern/

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

 

示例1:

输入: pattern = "abba"
, str = "dog cat cat dog"

输出: true

示例 2:

输入:pattern = "abba"
, str = "dog cat cat fish"

输出: false

示例 3:

输入: pattern = "aaaa"
, str = "dog cat cat dog"

输出: false

 

提示:

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

方法一：哈希表

这道题题目描述挺含糊的。

大概意思就是$pattern$中的一个字母唯一对应$s$中的一个单词。

但是DT的是C++里没有split。

因此C++选手需要手动模拟拆分字符串。

用一个记录上一个单词的起始位置的前一个位置，用一个变量记录遍历到了第几个单词，用两个哈希表分别存放单词和字母的对应关系。

每遍历到一个单词，就看是否和字母一一对应。

• 时间复杂度$O(n)$，其中$n$是字符串长度
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
public:
    bool wordPattern(string& pattern, string& s) {
        unordered_map<char, string> c2s;
        unordered_map<string, char> s2c;
        int th = 0;
        int lastBegin = -1;
        s += ' ';
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                string thisWord = s.substr(lastBegin + 1, i - lastBegin - 1);
                lastBegin = i;
                if (c2s.count(pattern[th])) {
                    if (c2s[pattern[th]] != thisWord) {
                        return false;
                    }
                }
                else {
                    c2s[pattern[th]] = thisWord;
                }
                if (s2c.count(thisWord)) {
                    if (s2c[thisWord] != pattern[th]) {
                        return false;
                    }
                }
                else {
                    s2c[thisWord] = pattern[th];
                }
                th++;
            }
        }
        return th == pattern.size();
    }
};
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

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126884583