题目描述
题目链接: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 |
|
- 时间复杂度: O(n) n 为
str
长度 - 空间复杂度: O(1) 虽然单词有组合有无数种,但是字母数量是常数