【leetcode】290. Word Pattern（Python & C++）

---

290. Word Pattern

题目链接

290.1 题目描述：

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 in pattern and a non-empty word in str.

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.

290.2 解题思路：

思路一：首先将str遍历，按照空格分开，放进vector中。判断vector的大小是否与pattern的长度一样，如果不一样，返回false。建立两个映射map，一个是char到string的，pattern映射到str；一个是string到char的，str映射到pattern。遍历pattern个长度，首先判断映射1，如果当前坐标下，映射1的值为空，则将vector同坐标下的string赋给映射1。否则判断映射1的值与vector同坐标下的string是否相同，如果不相同，则返回false。然后判断映射2，如果当前坐标下，映射2的值为空，则将pattern同坐标下的char赋给映射2。否则判断映射2的值与pattern同坐标下的char是否相同，如果不相同，则返回false。遍历结束后，返回true。

思路二：思想也是用到了映射，不过更为方便。首先，利用istringstream将str输入。这个的好处是直接按照空格处理字符串的输入。然后建立两个映射，一个是char到int的，一个是string到int的。意思是，如果同一坐标下，pattern中字符对应的坐标，与，str中字符串对应的坐标，如果相同，这说明匹配，如果不同，则不匹配。所以在循环中，如果发现两个映射的值不同，则返回false。然后将当前坐标下，两个映射的值置为i+1，之所以是i+1，不是i，是因为刚开始i是从0开始遍历的，而两个映射没进行赋值之前，其任何坐标下的值也是0，容易发生混淆。初次之外，为了防止pattern的长度与str中string的个数不同，在遍历时，如果发现i==pattern的长度（pattern短，str长），也返回false。当遍历结束，返回i==pattern的长度（如果长度不相同，说明pattern长，str短）

思路三：针对Python。思想差不多与思路二相同，但Python中字符串有自带函数处理分片问题，就s.split(str)就是将s中按照str分片，并且返回分片后一个列表。所以可以直接使用。并且可以利用map(function,sequence)，map(s.index,s)返回s中每个string的坐标，map(pattern.find,pattern)返回pattern中每个char的坐标，如果两者相同，则放回true，否则false。

290.3 C++代码：

1、思路一代码（0ms）：

class Solution109 { public: bool wordPattern(string pattern, string str) { map<char, string>m1; map<string, char>m2; vector<string>s; int f = 0; for (int i = 0; i < str.length();i++) { if (str[i] == ' ') { s.push_back(str.substr(f, i - f)); f = i + 1; } } s.push_back(str.substr(f, str.length() - f)); if (s.size() != pattern.length()) return false; for (int i = 0; i < pattern.length();i++) { if (m1[pattern[i]] == "") m1[pattern[i]] = s[i]; else if (m1[pattern[i]] != s[i]) return false; if (m2[s[i]] == NULL) m2[s[i]] = pattern[i]; else if (m2[s[i]] != pattern[i]) return false; } return true; } };

2、思路二代码（0ms）：

class Solution109_1 { public: bool wordPattern(string pattern, string str) { istringstream sw(str); map<char, int>p2i; map<string, int>s2i; string word; int i = 0; while (sw >> word) { if (i==pattern.length() || p2i[pattern[i]] != s2i[word]) return false; p2i[pattern[i]] = i + 1; s2i[word] = i + 1; i++; } return i == pattern.length(); } };

290.4 Python代码：

2、思路三代码（32ms）

class Solution(object): def wordPattern(self, pattern, str): """ :type pattern: str :type str: str :rtype: bool """ s=str.split(' ') return map(s.index,s) == map(pattern.find,pattern)

---