图解 | LeetCode #290 单词规律

作者丨木兄

来源丨编程狂想曲

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

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

示例1:

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

输出: true
示例2:
输入: pattern = "abba", str = "dog cat cat fish"
输出: false

思路分析
   

    根据示例分析可知，判断str是否遵循相同的规律，就是判断str中的每个单词是否和pattern中的每个字符有唯一的对应关系，即映射关系。
   
   

    在示例1中，字符a对应单词dog，字符b对应单词cat是一一映射关系；在示例2中，第一个字符a对应单词dog，第二个字符a对应单词fish，不是一一映射关系。
   
   

    因此，整体求解思路就是借助map来判断patter和str之间是否是一一对应的映射关系。
   
   

    若pattern和str是一一对应关系，则pattern中的字符个数和str中的单词个数是相同的。因此，当pattern中的字符个数和str中的单词个数不同时，结果肯定为false。如下图：
   
   

    
   
   

    当pattern中的字符个数和str中的单词个数相同时，接着就是遍历patter和str：
   
   

    若当前考察的pattern中的字符在map中不存在，但当前考察的str中的单词在map中存在，则表明已有其它字符和该单词对应，即多个字符对应同一个单词，直接返回false。如下图，字符a和字符b都对应单词dog；
   
   

    
   
   

    若当前考察的pattern中的字符在map中不存在，且当前考察的str中的单词在map中也存在，则将pattern中的字符作为key，str中的单词作为value存入map，建立两者间的映射关系；
   
   

    若当前考察的pattern中的字符在map中存在，但其对应的value和str中当前考察的单词不相同，则表明同一字符对应着多个单词，因此返回false。如下图，字符a既对应单词dog又对应单词cat；
   
   

    
   
   

    若上述考察没有返回，则表明pattern中的字符和str中的单词是一一对应关系，返回true。
   
   

    代码实现：
   
   

    
   

-End-

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！