江苏优质网站制作公司,深圳响应式网站建设哪家好,免费项目网站,中国核工业第五建设有限公司面试题目
给定一种规律 pattern 和一个字符串 s #xff0c;判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配#xff0c;例如#xff0c; pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 示例1:
输入: pattern abba, s …题目
给定一种规律 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
C代码
#include iostream
#include string
#include unordered_map
using namespace std;/*
* 单词规律的判断和同构字符串相似
* 使用两个无序哈希表保存映射关系
* 设置一个临时变量保存单词
* 如果单词和字符有之间映射关系但是值不同返回false
*/
bool wordPattern(string pattern, string s) {unordered_mapstring, char s2c;unordered_mapchar, string c2s;int len s.size();int i 0;for (auto c : pattern) {if (i len) {return false;}int j i;while (j len s[j] ! ) j;const string tmp s.substr(i, j - i);if (s2c.count(tmp) s2c[tmp] ! c || c2s.count(c) c2s[c] ! tmp) {return false;}s2c[tmp] c;c2s[c] tmp;i j 1;}return true;
}
int main() {string pattern abba;string s dog cat cat dog;bool ans wordPattern(pattern, s);cout boolalpha ans endl;return 0;
}
分析
单词规律的判断和同构字符串相似使用两个无序哈希表保存映射关系设置一个临时变量保存单词如果单词和字符有之间映射关系但是值不同返回 false。
问题
subsrt(pos, len) 函数表示从 pos开始 拷贝 len 个字符。
