LeetCode 290. Word Pattern双map *****

一、题目

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 inpattern and anon-empty word instr.

Examples:

pattern = "abba", str = "dog cat cat dog" should return true.pattern = "abba", str = "dog cat cat fish" should return false.pattern = "aaaa", str = "dog cat cat dog" should return false.pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

题意：

给定一种模式和一个字符串，看字符串模式和给定的模式是否一致。

注意：同样字符串的题，考虑字符集范围。

          题目给出模式仅仅包含小写字母，并且str也是仅仅包含小写字母且由一个空格隔开。

二.我的思路

           效率不行，好在自己能做出来

          1.预处理：将字符串str按照空格分割，存入到vector中，方便之后的操作。关于按照字符分割有很多种方法，之后会介绍。我使用的是一种通用的分割，可以按照指定的字符进行分割，编写出来较为复杂。

         参考博客：http://write.blog.csdn.net/postedit/71329987             

                         http://blog.csdn.net/infoworld/article/details/18986255

          2.对比模式的长度和预处理之后vector的长度。不相等那么就肯定不一样.

          3.我能想到的是以pattern[i]为键，以vector[i]为值，当pattern[i]为键不在map中且vector[i]为值不在map中，才进行更新map操作。当以pattern[i]的键不在而值在，说明两个键对应一个值，直接返回false.      

           关键点：在map中查找值是否存在     http://www.cnblogs.com/xufeiyang/archive/2012/05/09/2491871.html

          4.当pattern[i]的键存在，但是其值和vector[i]不一样也返回false。

          5.当一一对应关系相等返回true.

class Solution { public: class map_value_finder //map按照值来查找是否存在 { public: map_value_finder(const std::string &cmp_string) :m_s_cmp_string(cmp_string){} bool operator ()(const std::map<char, std::string>::value_type &pair) { return pair.second == m_s_cmp_string; } private: const std::string &m_s_cmp_string; }; bool wordPattern(string pattern, string str) { // if(pattern == str) return true; char *str1 = new char[str.size()]; int i; for (i = 0; i < str.size(); i++) { str1[i] = str[i]; } str1[i] = '\0'; const char *split = " "; char *p; p = strtok(str1, split); vector<string> vecStr; while (p != NULL) { vecStr.push_back(p); p = strtok(NULL, split); } if (vecStr.size() != pattern.size()) { return false; } unordered_map<char, string> equal; for (int i = 0; i < pattern.size();i++) { auto iter = equal.find(pattern[i]); if (iter == equal.end()) { if (find_if(equal.begin(), equal.end(), map_value_finder(vecStr[i])) != equal.end()) { return false; } equal[pattern[i]] = vecStr[i]; continue; } if (iter->second != vecStr[i]) { //cout << "No" << endl; return false; } } //cout << "yes" << endl; return true; } };

参考思路：

          1.看是字符串和模式是否匹配，应用键值对map数据结构。在操作数据结构之前，需要做一个预处理

          2.预处理：将字符串str按照空格分割，存入到vector中，方便之后的操作

          3.判断pattern的长度和vector的长度是否一致，不一致返回false.

          4.使用两个map。一个以pattern作为键以vector作为值，一个以vector作为键以pattern作为值

          5.只有当vector作为键和pattern作为键的两个map函数都不存在的情况下，加入.

          6.否则比较vector[i]作为键的值和pattern[i]是否一致。不相等返回false.

class Solution { public: bool wordPattern(string pattern, string str) { istringstream strcin(str); string s; vector<string> vs; while(strcin >> s) vs.push_back(s); if (pattern.size() != vs.size()) return false; map<string, char> s2c; map<char, string> c2s; for (int i = 0; i < vs.size(); ++i) { if (s2c[vs[i]] == 0 && c2s[pattern[i]] == "") { s2c[vs[i]] = pattern[i]; c2s[pattern[i]] = vs[i]; continue; } if (s2c[vs[i]] != pattern[i]) return false; } return true; } };

四、总结比较

          相比较之下，三的思路巧妙就在双map，使用map<string,char>来看vector[i]作为键是否存在，而不需要像我那样在map中查找值是否存在。

查看某键是否存在我是通过find来看。三利用map的一个特性，当map中不存在某键，使用之后会将该键插入到map中值为默认值(int为0,char为0'\0'，string为0'\0')。

三中只要pattern[i]作为键或者vector[i]作为键存在，只要他们的键值对不等就返回false