290. Word Pattern

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.

使用unordered_map，时间复杂度O(n)：

class Solution { public: bool wordPattern(string pattern, string str) { const int len1 = pattern.length(); const int len2 = str.length(); if(len1 == 0 && len2 == 0) return true; if(len1 == 0 || len2 == 0) return false; unordered_map<char, string> umap1; unordered_map<string, char> umap2; int j = -1, i = 0; for(i=0; i<len1; ++i){ int c = j + 1; while(str[++j] != ' ' && str[j] != '\0'); string tmp(str, c, j-c); auto it1 = umap1.insert(make_pair(pattern[i], tmp)); auto it2 = umap2.insert(make_pair(tmp, pattern[i])); if(!it1.second || !it2.second){ if(it1.first->second != tmp || it2.first->second != pattern[i]) return false; } if(str[j] == '\0') //注意为'\0'的情况 break; } return j == str.length() && i == pattern.length()-1; //注意两个匹配长度不能的情况 } };