题目:
给定一种规律 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 中每个单词都被 单个空格 分隔
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/word-pattern
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
参考@蓝色北半球的题解
题中的双向连接:
如果是从pattern到str的单向连接的话:那么意味着"a"只对应着"dog",但"dog"就可以对应多个字符,它可能除了"a"之外也对应着别的字符。因此,abba与"dog dog dog dog"符合单向连接的对应规律。在这里a只对应"dog",但"dog"同时对应着"a"和"b";
而双向连接意味着,"a"只对应着"dog",且"dog"也只对应着"a",因此在双向连接的对应规律下,上述的abba与"dog dog dog dog"是匹配失败的,只有abba与"dog cat cat dog"这种可以匹配成功。
使用HashMap+HashSet:
1.先将给定的s以空格为分隔符,分割成单个字符串,存放在字符串数组strs中。例如:将"dog cat cat dog"分隔成["dog", "cat", "cat", "dog"]
2.再准备一个哈希表map,哈希表的key记录着pattern中的字符,哈希表的value记录着strs数组中的字符串;
3.再准备一个hashSet,来存放strs中的单词(无重复),用来保证每个单词所对应的pattern字符是唯一的;
4.首先判断pattern的长度是否与字符串数组strs的长度相等,不相等,直接返回false;
5.然后遍历字符串pattern,对于每一个位置i:
-
如果map之前加入过pattern[i]这个key,那么只需要检查这个key对应的value是否与str[i]相等即可;
-
如果map中之前没加入过pattern[i]这个key:
-
但是set中已经有了arr[i]这个单词,说明arr[i]这个value不止和当前的key对应,它曾经也和别的key对应过,不符合题目中要求的双向连接的规律,返回false;
-
否则,把pattern[i]和arr[i]这二者的对应关系加入map。
-
java代码:
1 class Solution { 2 public boolean wordPattern(String pattern, String s) { 3 //以空格为分隔符进行分割 4 String[] strs = s.split(" "); 5 //如果两个字符串长度不一样一定不匹配 6 if (pattern.length() != strs.length) return false; 7 Map<Character, String> map = new HashMap<>(); 8 HashSet<String> set = new HashSet<>(); 9 for(int i = 0; i < pattern.length(); i++){ 10 char c = pattern.charAt(i); 11 if(map.containsKey(c)){ 12 //如果当前key,就判断value与当前单词是否匹配 13 if(!map.get(c).equals(strs[i])){ 14 return false; 15 } 16 }else{ 17 //如果map中还没有c这个key,但是已经有strs[i]这个value 18 //说明strs[i]这个value之前已经和别的key对应过 19 //这就不符合双向连接 20 if(set.contains(strs[i])){ 21 return false; 22 } 23 24 map.put(c, strs[i]); 25 set.add(strs[i]); 26 } 27 } 28 return true; 29 } 30 }