290. 单词规律

1. 题目

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

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

示例1:

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

示例 2:

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

示例 3:

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

提示:

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

2. 思路

Tips: 整体思路与205. 同构字符串一致

  • 将字符串s按照空格进行切割为字符串数组，同时将pattern转为字符数组
  • 判断以上俩数组是否一致，如果数组长度不一致其实不可能遵循相同的规律，则可直接返回false
  • 遍历数组，初始化patternMap与strMap哈希表，用于存储当前字符串的上一次出现下标
  • 如果上一次出现的下标比对失败，则说明不遵循一致规律，则可直接返回false
  • 比对的过程需要注意，由于使用的下标存储的是Integer对象，其中Integer默认1-128采用的是同地址，128以上的数值则会出现地址不一致，然而直接用=号做判断会出现异常，因此Integer类型需要使用equals来做判断

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean wordPattern(String pattern, String s) {
        var strArray = s.split(" ");
        var patternArray = pattern.toCharArray();
        var patternMap = new HashMap<Character, Integer>();
        var strMap = new HashMap<String, Integer>();
        var length = strArray.length;

        if (strArray.length != patternArray.length) {
            return false;
        }

        for (var i = 0; i < length; ++i) {
            var strLastIndex = strMap.getOrDefault(strArray[i], 0);
            var patternLastIndex = patternMap.getOrDefault(patternArray[i], 0);

            if (!patternLastIndex.equals(strLastIndex)) {
                return false;
            }

            strMap.put(strArray[i], i + 1);
            patternMap.put(patternArray[i], i + 1);
        }

        return true;
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230827160311523