单词规律

题目

290. 单词规律

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

题解

题解一（普通方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static boolean wordPattern(String pattern, String s) {
    HashMap<String, String> hashMap = new HashMap<>();
    String[] split = s.split(" ");
    if (split.length != pattern.length()) {
        return false;
    }

    for (int i = 0; i < split.length; i++) {
        hashMap.put(String.valueOf(pattern.charAt(i)), split[i]);
    }
    Set<String> strings = hashMap.keySet();
    List<String> values = hashMap.values().stream().distinct().toList();
    if (strings.size() != values.size()) {
        return false;
    }
    for (int i = 0; i < split.length; i++) {
        if (!hashMap.get(String.valueOf(pattern.charAt(i))).equals(split[i])) {
            return false;
        }
    }
    return true;
}

image-20241121205812178

题解二（我尼玛，写这个解法的人简直是个天才）

利用同一个元素的下标一样的原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean wordPattern(String pattern, String s) {
    List<String> strs = Arrays.asList(s.split(" "));
    int n = pattern.length();
    if (n != strs.size()) {
        return false;
    }

    for (int i = 0; i < n; i++) {
        char ch = pattern.charAt(i);
        int i2 = pattern.indexOf(ch);
        String o = strs.get(i);
        int i1 = strs.indexOf(o);
        // System.out.println(ch + " " + i2 + "  <=====>  " + o + " " + i1);
        if (i2 != i1) {
            return false;
        }
    }
    return true;
}

image-20241121210700301