题解 | #牛群智能指导系统#

知识点

哈希

思路

用map维护左侧pattern字符串的每一个char字符到右侧plan字符串中的每一个字符中的映射。注意映射的顺序，例如 aaaa 对YUAN YUAN SHEN SHEN ，如果反向映射的话，需要在映射前检查映射结果是否已经存在过，会导致时间复杂度的上升。

回到笔者做法，对于pattern中每一个字符，若合法就只会对应一个plan中字符串，所以我们同步枚举字符串和字符，检查他们的映射匹配性就可以： 若映射不存在，则建立映射

若存在，则检查是否匹配，不匹配直接返回false了

若检查完毕仍无false，则返回true

详解看代码注释。

代码c++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pattern string字符串
     * @param plan string字符串
     * @return bool布尔型
     */
    bool isValidPattern(string pattern, string plan) {
        // write code here
        map<char, string>mp;//字符到字符串
        map<char, int>mp2;//判断是否已对字符建立过映射
        int idx = 0;//pattern下标，从0开始
        string s = "";//原字符串为空
        for (int i = 0; i < plan.size(); i++) {
            if (plan[i] == ' ') {//遇到空格了，字符串完成收集，开始检查
                //  cout << s << "  " << mp2[pattern[idx]] << "  " << mp[pattern[idx]] << endl;
                if (mp2[pattern[idx]] == 0) {
                  //未建立映射。建立一下并标记
                    mp[pattern[idx]] = s;
                    mp2[pattern[idx]] = 1;

                } else {
                //已建立，检查一不一样，不一样返回false
                    if (mp[pattern[idx]] !=s) {                 
                        return false;
                    }
                }

                s = "";//检查完毕，清空字符串
                idx++;//pattern字符串下标右移，到下一个字符
            }

            else  s += plan[i];//不为空格，继续收集字符串
        }
        //注意这个再判一次，因为最后一个字符串后面是没有空格的，收集完手动判就行了
        if (mp2[pattern[idx]] == 0) {
            mp[pattern[idx]] = s;
            mp2[pattern[idx]] = 1;

            idx++;
        } else {
            if (mp[pattern[idx]] != s) {
                return false;
            }
        }

        return true;//一直都没return false，那就return true
    }

};
};