给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。
这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。
示例1:
输入: pattern = "abba", str = "dog cat cat dog" 输出: true示例 2:
输入:pattern = "abba", str = "dog cat cat fish" 输出: false示例 3:
输入: pattern = "aaaa", str = "dog cat cat dog" 输出: false示例 4:
输入: pattern = "abba", str = "dog dog dog dog" 输出: false建立两个哈希表，双向对应
#include<iostream> #include<unordered_map> #include<string> using namespace std; class Solution{ public: bool wordPattern(string& pattern, string& str) { vector<string> words=split(str); if (pattern.size() != words.size()) return false; unordered_map<char, string> map1; unordered_map<string, char> map2; for (int i = 0; i < pattern.size(); i++) { if (map1.count(pattern[i])>0 && map1[pattern[i]] != words[i]) return false; if (map2.count(words[i]) > 0 && map2[words[i]] != pattern[i]) return false; map1[pattern[i]] = words[i]; map2[words[i]] = pattern[i]; } return true; } vector<string> split(const string& str) { vector<string> res; string temp; for (int i = 0; i <= str.size(); i++) { if (str[i] == ' ' || str[i] == '\0') { res.push_back(temp); temp.clear(); } else { temp += str[i]; } } return res; } }; int main() { string pattern = "abba"; string str = "cat dog dog cat"; bool reslut = Solution().wordPattern(pattern, str); if (reslut) { cout << "true"; } else { cout << "false"; } system("pause"); return 0; }
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add" 输出: true示例 2:
输入: s = "foo", t = "bar" 输出: false示例 3:
输入: s = "paper", t = "title" 输出: true#include<iostream> #include<unordered_map> #include<string> using namespace std; class Solution { public: /** * @param s: a string * @param t: a string * @return: true if the characters in s can be replaced to get t or false */ bool isomorphic(string &s, string &t) { unordered_map<char, char> m1; //s --> t unordered_map<char, char> m2; //t --> s for (int i = 0; i < s.size(); i++) { if (m1.count(s[i]) > 0 && m1[s[i]] != t[i]) return false; if (m2.count(t[i]) > 0 && m2[t[i]] != s[i]) return false; m1[s[i]] = t[i]; m2[t[i]] = s[i]; } return true; } }; int main() { string s = "paper"; string t = "title"; bool reslut = Solution().isIsomorphic(s, t); if (reslut) cout << "true"<<endl; else cout << "false"<<endl; system("pause"); return 0; }
