本文共 2150 字，大约阅读时间需要 7 分钟。

题目

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.

解题

意思就是给你一个pattern字符串，给你一个str字符串，看它们是否对应匹配。注意这里，pattern里如果有空格，也被当做一个有效的字符串，而str里如果有空格，是起把两个字符串分开的作用，空格不算做字符串里面的内容。

复杂的AC代码

class Solution {
  //有编程测试public:    bool wordPattern(string pattern, string str) {        unordered_map
   
     m;        unordered_map
    
      mm;//判断str是否存在某个字符串        int len1=pattern.length();        int len2=str.length();        if(len1==0||len2==0) return false;        int count=0;        for(int i=0;i
    
   

思路：

开始我是不知道有istringstream这个大杀器，所以做的时候就没用这个，而是逐字符逐字符进行的。

先是搜索str，遇到字符串存成new_s，遇到空格跳过。

//先找到一串字符，不包括空格            while(i

这样我们找到了str中一个的字符串，此时我们要搜索pattern，看看pattern中对应的那个字符是否和该字符串对应，注意，这里的“对应”我采用unordered_map，map里的key表示pattern的字符，map里的value表示刚刚找到的字符串。

unordered_map
   
     m;
   

if(count

上面的代码有一个变量是mm，它是来存储str中字符串出现的次数的，key是string，value是string出现的次数。

如果pattern中第count个字符（其实现在求取得news也是第count个字符串）已经在m中，那么判断现在的news是否在mm中，不在肯定直接false，在的话，就让其出现的值++，接下来匹配m中pattern[count]这个字符对应的字符串是否是news，不是直接false，是的话，就继续。

紧接着分析count>=len1的情况，也就是pattern已经遍历完了

那么就要判断str中是否还有字符串，有的话就返回false，没有返回true。

else//超过长度，那么剩下的str只可能是空才有可能返回true            {                while(i

在循环最后，要更新i，因为i是下一次循环字符串的起点，来寻找下一个字符串。

i = index_end;//i要换到这个字符串之后

当遍历str完了之后，如果pattern还有字符串，那么返回false。

上述所有都没问题，我们可以认为匹配！

简单的AC代码

bool wordPattern(string pattern, string str) {    map
   
     p2i;    map
    
      w2i;     in(str);    int i = 0, n = pattern.size();    for (string word; in >> word; ++i) {        if (i == n || p2i[pattern[i]] != w2i[word])            return false;        p2i[pattern[i]] = w2i[word] = i + 1;    }    return i == n;}
    
   

关于istringstream

转载地址：http://qexvi.baihongyu.com/