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

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。 示例1: 输入: pattern = “abba”, str = “dog cat cat dog” 输出: true 示例 2: 输入:pattern = “abba”, str = “dog cat cat fish” 输出: false 示例 3: 输入: pattern = “aaaa”, str = “dog cat cat dog” 输出: false 示例 4: 输入: pattern = “abba”, str = “dog dog dog dog” 输出: false 说明: 你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。 思考与分析： 匹配：字符串str中的单词与pattern中的字符一一对应 1、当拆解出一个单词时，若该单词已经出现，则当前单词对应的pattern字符必为该单词曾经对应的pattern字符 2、当拆解出一个单词时，若该单词未曾出现，则当前单词对应的pattern字符必为该单词对应的pattern字符也必须未曾出现 3、单词的个数与pattern字符串中的字符数量相同 算法思路： 1、设置单词(字符串)到pattern字符的映射；使用数组used[128]记录pattern字符是否使用 2、遍历str，按照空格拆分单词，同时对应的向前移动指向pattern字符的指针，每拆分出一个单词，判断：

if(该单词从未出现在单词表中){
   	如果当前的pattern以被使用，则返回false;	将单词与当前指向的pattern字符做映射;	标记当前指向的pattern字符已使用}else{
   	如果当前的单词在哈希表中的映射字符不是当前指向的pattern字符,则返回false}

3、若单词个数与pattern字符个数不匹配，返回false

代码如下：

class Solution {
   public:    bool wordPattern(string pattern, string str) {
           std::map
   
     word_map;   //单词到pattern字符的映射        char used[128] = {
   0};    //记录已被映射的pattern字符        std::string word;    //临时保存拆分出的单词        int pos = 0;   //当前指向的pattern字符        str.push_back(' ');  //str尾部push一个空格，使遇到空格拆分单词        for (int i = 0; i < str.length(); i++){
               if (str[i] == ' '){
     //遇到空格即拆分出一个单词                if (pos == pattern.length()){
     //若分隔出一个单词，但没有pattern字符对应                    return false;                }                if (word_map.find(word) == word_map.end()){
      //若单词未出现在哈希映射中                     if (used[pattern[pos]]){
       //如果当前pattern字符已使用                        return false;                    }                    word_map[word] = pattern[pos];   //建立映射                    used[pattern[pos]] = 1;     //标记被使用过                }                else{
                       if(word_map[word] != pattern[pos]){
      //若word已经建立映射，无法与当前pattern字符对应                        return false;                    }                }                word = "";   //完成一个单词的插入和查询后，清空word                pos++;    //指向pattern字符的pos指针前移            }            else{
                   word += str[i];            }        }        if(pos != pattern.length()){
       //有多余的pattern字符            return false;        }        return true;    }};
   

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