【LeetCode面试150】——209单词规律
博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：简单
默认优化目标：最小化时间复杂度。
Python默认为Python3。
目录
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 False
for word,ch in zip(words,pattern):#键值对
if(word in str2ch and str2ch[word]!=ch or ch in ch2str and ch2str[ch]!=word):
return False
str2ch[word]=ch
ch2str[ch]=word
return True参考文献
原文地址：https://blog.csdn.net/Junmo12345/article/details/142487581
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！