0%

[Leetcode]290. Word Pattern(C++)

题目描述

题目链接:290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

例子

例子 1

Input: pattern = “abba”, str = “dog cat cat dog”
Output: true

例子 2

Input: pattern = “abba”, str = “dog cat cat fish”
Output: false

例子 3

Input: pattern = “aaaa”, str = “dog cat cat dog”
Output: false

例子 4

Input: pattern = “abba”, str = “dog dog dog dog”
Output: false

Note

You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

解题思路

首先从字符串中获取单词很简单,通过一个指针以空格为分界线遍历即可。这里考虑到需要建立字母和单词之间的对应关系,很容易想到使用哈希表。同时注意对应是关系是双向的,意味着 单词->字母 和 字母->单词 都需要一一对应,因此需要建立两个哈希表存储两边对应关系。同时因为对应关系都两侧都必须非空,因此还要判断 pattern 中的字符和 str 中的单词数是否一致,可以在遍历完 pattern 后判断遍历 str 的指针是否已指向末尾即可,代码如下:

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
#include <string>
#include <unordered_map>

class Solution {
public:
bool wordPattern(std::string pattern, std::string str) {
std::unordered_map<char, std::string> dist;
std::unordered_map<std::string, char> rev_dist;
int ptr = 0;
for (int i = 0; i < pattern.length(); i++) {
char key = pattern[i];
std::string word = "";
while (ptr < str.length() && str[ptr] == ' ') ptr++;
while (ptr < str.length() && str[ptr] != ' ') {
word += str[ptr];
ptr++;
}
if (word.empty()) return false;

if (dist.find(key) == dist.end()) {
dist[key] = word;
} else if (dist[key] != word) {
return false;
}
if (rev_dist.find(word) == rev_dist.end()) {
rev_dist[word] = key;
} else if (rev_dist[word] != key) {
return false;
}
}
if (ptr != str.length()) return false;

return true;
}
};
  • 时间复杂度: O(n) n 为 str 长度
  • 空间复杂度: O(1) 虽然单词有组合有无数种,但是字母数量是常数