【LeetCode面试150】——209单词规律
博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：简单
默认优化目标：最小化时间复杂度。
Python默认为Python3。
目录
1 题目描述
2 题目解析
3 算法原理及代码实现
参考文献
1 题目描述
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", s = "dog cat cat dog" 输出: true
示例 2:
输入:pattern = "abba", s = "dog cat cat fish" 输出: false
示例 3:
输入: pattern = "aaaa", s = "dog cat cat dog" 输出: false
提示:
-
1 <= pattern.length <= 300 -
pattern只包含小写英文字母 -
1 <= s.length <= 3000 -
s只包含小写英文字母和' ' -
s不包含 任何前导或尾随对空格 -
s中每个单词都被 单个空格 分隔
2 题目解析
输入是两个字符串pattern和s，pattern表示规律，s是字符串。输出是布尔值。约束条件是判断s是否符合规律pattern，是返回true，否返回false。
3 算法原理及代码实现
该题目等价于pattern中的单词和s中的单词一一对应，用空格来区分单词。我们创建两个哈希表str2ch和ch2str，用来记录这种对应关系。如果它们不是一一对应关系，返回false；否则返回true。
时间复杂度为O(n+m)，n为pattern的长度，m为s的长度。空间复杂度为O(n+m)。
C++代码实现
class Solution {
public:bool wordPattern(string pattern, string s) {unordered_map<string, char> str2ch;unordered_map<char, string> ch2str;int i=0;int m=s.size();
for(auto ch : pattern){if(i>=m){//i=0开始return false;}int j=i;while(j<m && s[j]!=' ') j++;const string &tmp=s.substr(i,j-i);//避免拷贝if(str2ch.count(tmp) && str2ch[tmp]!=ch){return false;}if(ch2str.count(ch) && ch2str[ch]!=tmp){return false;}str2ch[tmp]=ch;//哈希表赋值ch2str[ch]=tmp;i=j+1;}
return i>=m;
}
};Python代码实现
class Solution:def wordPattern(self, pattern: str, s: str) -> bool:str2ch=dict()#用字典构建哈希表ch2str=dict()words=s.split()
if(len(words)!=len(pattern)):return Falsefor word,ch in zip(words,pattern):#键值对if(word in str2ch and str2ch[word]!=ch or ch in ch2str and ch2str[ch]!=word):return Falsestr2ch[word]=chch2str[ch]=word
return True参考文献
力扣面试经典150题
力扣官方题解