题目

给定一种规律 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 中每个单词都被 单个空格 分隔

题解

这题其实和[205 同构字符串](LeetCode-205-同构字符串 - Ther’s World (excelius.xyz))很像的，需要建立pattern->s和s->pattern的映射。这里我们要清楚pattern的长度和s单词的个数应该是对应的，不然要return false。然后我们挨个遍历就好了，遇到没有出现过的加入哈希表，如果出现过但是不相等return false，如果有一个没查到说明对不上return false。最后是91%时间复杂度，还可以~(●ˇ∀ˇ●)

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
28
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] sArray = s.split(" ");
        HashMap<Character, String> p2s = new HashMap<>();
        HashMap<String, Character> s2p = new HashMap<>();
        if (pattern.length() != sArray.length) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            // 模式的每个字符都匹配上一个单词
            String valueString = p2s.get(pattern.charAt(i));
            Character valueChar = s2p.get(sArray[i]);
            // 如果不为空，说明能找到，如果为空，说明没有
            if (valueString != null && valueChar != null) {
                // 能找到但是不相等
                if (!valueString.equals(sArray[i]) || !valueChar.equals(pattern.charAt(i))) {
                    return false;
                }
            } else if ((valueChar == null && valueString != null) || (valueChar != null && valueString == null)) {
                return false;
            } else {
                p2s.put(pattern.charAt(i), sArray[i]);
                s2p.put(sArray[i], pattern.charAt(i));
            }
        }
        return true;
    }
}