稀碎从零算法笔记Day21-LeetCode:单词规律

题型：哈希表、字符串

链接：290. 单词规律 - 力扣（LeetCode）

来源：LeetCode

题目描述

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

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

题目样例

示例1:

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

示例 2:

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

示例 3:

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

提示:

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

题目思路

之前做过一个字母映射字母的题目，用的是两个 unordered_map<char,char>。这里可以模仿一下——两个unordered_map，但是一个是<string,char>,以为string映射到char，另一个相反<char,string>。

思路就是遍历模式串，没遍历一个字母的时候，就从字符串s截取一个单词(单词截取思路可以是双指针，然后创一个string存起来)，截完后可以看下两个无序图中有无键值对，有的话看一下是否一一对应，不对应的话就可以直接return 0，对应或者没有的话就更新两个无序图

C++代码

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        // 映射：两个哈希表，实现 单词 - 字符间的一一对应
        // ① 提取单词   ②单词和字符映射
        unordered_map<char,string> c2s;
        unordered_map<string,char> s2c;
        int lenp=pattern.length(),lens=s.length();
        int i=0;
        int begin=0,end=0;
        while(i < lenp)
        {
            if(begin >= lens)
                return 0;
            while(end < lens && s[end] != ' ' )
                end++;
            string temp = s.substr(begin,end-begin);
            char temp_ch = pattern[i];
            // 映射失败：字符 和 单词不对应
            if((c2s.count(temp_ch) && c2s[temp_ch] != temp) || (s2c.count(temp) && s2c[temp] != temp_ch))
                return 0;
            c2s[temp_ch] = temp;
            s2c[temp] = temp_ch;
           
           begin = end+1;
           end=begin;
           i++;
           
        }
        return begin == lens+1;
    }
};