Come from : [https://leetcode-cn.com/problems/word-pattern/]

290. Word Pattern

1.Question2.Answer3.我的收获

1.Question

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.

Example 1 :

Input: pattern = "abba", str = "dog cat cat dog" Output: true

Example 2 :

Input:pattern = "abba", str = "dog cat cat fish" Output: false

Example 3 :

Input: pattern = "aaaa", str = "dog cat cat dog" Output: false

Example 4 :

Input: pattern = "abba", str = "dog dog dog dog" Output: false

Note:

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

2.Answer

easy 类型题目（我感觉并不easy~）。用 字符哈希表。 下面是思路，我的代码里 也有详细的 注释，分享给大家。

分析例子，总结规律：

str与pattern数量相同拆解出一个str单词时，若该单词在str已经出现，则该单词对应的pattern字符必须是曾经对应的pattern字符拆解出一个str单词时，若该单词在str未出现，则该单词对应的pattern字符必须未出现 很明显这是一种及其强烈的映射关系，本题我们考虑str----pattern的映射

算法思路：str=“dog cat cat *” pattern=“abb？”

设置单词str到pattern’的哈希映射，使用数组used[128]记录pattern字符是否使用遍历str，按照空格拆分单词，同时对应移动pattern的指针，判断 如果该单词从未出现在哈希表： 如果pattern的used使用了，false 否则当前单词与pattern作映射，并且used标记 否则 如果当前哈希表单词映射不是指向pattern字符，falsestr pattern数量不匹配 false 总体说：就是同时遍历两个集合，未出现作映射，都出现过作判断，全部遍历后看数量。

AC代码如下：

class Solution { public: bool wordPattern(string pattern, string str) { map<string, char> word_map; char used[128] = {0}; //保存映射的pattern字符 int pos = 0; //相当于指针，指向 pattern string word; //拆分出的单词 str.push_back(' '); //在最后加个空格，方便拆分单词 for(int i = 0; i < str.length(); ++i) { if(str[i] == ' ') { // 拆分出单词后 分为 以下几种情况： // 1 如果 pattern 比 str 长度小，即：单词还没拆分完，pattern没了。比如反例：str=“dog fish” pattern=“a” if(pos == pattern.length()) { return false; } // 2. 若单词 未出现 在 哈希映射中 if(word_map.find(word) == word_map.end()) { // 2.1 判断当前字符是否已被使用.若 被 使用，则返回false if(used[pattern[pos]]) //比如反例：str=“dog cat cat fish”， pattern=“abba” { return false; } // 2.2 若没有被使用，更新 哈希映射 word_map[word] = pattern[pos]; used[pattern[pos]] = 1; } else //3. 若单词 出现 在 哈希映射中 { // 3.1 若当前 word 映射已经建立，但是无法 与pattern 匹配,则 返回 fasle if(word_map[word] != pattern[pos]) { return false; //比如反例：str=“dog cat cat fish”， pattern=“abca” } } word = ""; //完成 一个单词的 判断后， 清空word ++pos; //指向 pattern 字符的指针后移 } else { word += str[i]; } } //4 有多余的 pattern字符。 比如反例：str=“dog”， pattern=“aab” if(pos != pattern.length()) { return false; } return true; } };

3.我的收获

感觉还是要系统的掌握知识。。。 比如这次的 哈希表 day2。。。 系统的学习之后，才能更加得心应手的运用~

2019/5/26 胡云层 于南京 87