【leetcode面试经典150题】41. 单词规律（C++）

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主，题解使用C++语言。（若有使用其他语言的同学也可了解题解思路，本质上语法内容一致）

【题目描述】

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

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

【示例一】

输入: pattern = "abba", s = "dog cat cat dog"

输出: true

【示例二】

输入:pattern = "abba", s = "dog cat cat fish"

输出: false

【示例三】

输入: pattern = "aaaa", s = "dog cat cat dog"

输出: false

【提示及数据范围】

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

【代码】

// 构造双射哈希，同步判断和更新

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> p2s;    // pattern中的字符到s中的字符子串的映射表
        unordered_map<string, char> s2p;    // s中的字符字串到pattern中的字符的映射表
        int n = pattern.size();
        int m = s.size();
        int wordStart = 0;  // 单词的起点索引
        int wordEnd = 0;    // 单词的终点索引（边界或指向空格）
        char ch;            
        string word;
        for(int i = 0; i < n; i++){
            if(wordStart >= m)return false;     // 单词起点已经到达边界，说明s中的单词遍历完了；而pattern的字符还有，字符数量多余单词数，不匹配
            while(wordEnd < m && s[wordEnd] != ' ')wordEnd++;   // wordEnd右移直到到达s边界或者分割的空格
            word = s.substr(wordStart, wordEnd - wordStart);    // 截取单词
            ch = pattern[i];    // 获取当前字符
            if((p2s.count(ch) && p2s[ch] != word) || (s2p.count(word) && s2p[word] != ch)){
                // 字符与单词没有一一映射：即字符记录的映射不是当前单词或单词记录的映射不是当前字符
                return false;
            }
            // 更新映射，已存在的映射更新后仍然是不变的；不存在的映射将被加入
            p2s[ch] = word; 
            s2p[word] = ch;
            // 更新单词区间，起点为当前终点的下一个位置；终点初始与起点相同
            wordStart = wordEnd + 1;
            wordEnd = wordStart; 
        }
        // 如果pattern遍历结束后，字符串s也遍历结束（即单词起点到达了边界），则二者匹配；
        // 否则s还有单词没有匹配，字符数与单词数不匹配
        return wordStart == m + 1;  
    }
};