Problem
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
1 | Example 1: |
Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
Solution
Analysis
模式匹配问题.
给定两个字符串:pattern,str. 其中str是用单个空格切分的字符串,判断两个字符串模式是否匹配. 匹配: 双射. a->b, b->a.
有一个需要注意的是,两者的对应关系并不是对等的,不是char -> char, 而是 char-> string. 而string则是str中用空格切分出来的子串,所以需要找到这样的由空格切分的子串数组,匹配问题就是一个hash表映射的问题,确保a2b,以及b2a都是正确的.
- 如果当前字符出现在hash表中,判断当前对应关系和hash表中的记录结果是否一致,如果一致,则继续判断;如果不一致,返回false;
- 如果当前字符没有出现在hash表中,则记录这对对应关系;
匹配(双射),本质上还是一个函数.
具体实现,我们可以将结果都映射到同一个参考系上(做一次抽象,比如都是AABB型),然后做对比. 也可以相互映射,同时判断各自的映射结果(这里的实现方法就是相互映射,同时判断).
此外还要注意corner case, 两个字符串存在空串情况,返回false.
Code
1 | class Solution { |
1 | class Solution { |