单词规律

发表于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

LeetCode每日一题，290. Word Pattern

先看题目描述

rQ4vwt.png

大意就是给定一个模式串 pattern 和一个字符串 s，让我们判断 s 是否能匹配 pattern

算法和思路

哈希表

我们可以使用哈希表，以 pattern 中的字母作为键，s 中的字符串作为值，来判断是否能匹配

算法流程

  • 将 s 根据空格分割为一个字符串数组 ss，初始化一个哈希表 map，判断 ss 的长度与 pattern 的长度是否相等，不相等的话则直接返回 false
  • 用指针 i 来遍历 pattern 和 ss
    • 将 pattern.charAt(i) 作为 key，若 map 的所有键中 key 不存在，再去判断 map 的所有 value 中是否存在 ss[i]，若存在则直接返回 false，不存在的话就将 key 和 ss[i] 作为键值对放入 map 中；若 map 的所有键中存在 key，则判断该键所对应的值是否与 ss[i] 相等，若不相等的话则直接返回 false
  • 若最后遍历结束后也没返回，说明到达终态，s 与 pattern 能匹配，返回 true

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] ss = s.split(" ");
        if (ss.length != pattern.length()) {
            return false;
        }
        Map<Character, String> map = new HashMap<>();
        for (int i = 0; i < ss.length; i++) {
            Character key = pattern.charAt(i);
            if (!map.containsKey(key)) {
                if (map.containsValue(ss[i])) {
                    return false;
                }
                map.put(key, ss[i]);
            } else {
                if (!map.get(key).equals(ss[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

下面是题解的代码，使用了两个哈希表，时间复杂度要低些

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
29
class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch2str = new HashMap<Character, String>();
        int m = str.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); ++p) {
            char ch = pattern.charAt(p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str.charAt(j) != ' ') {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch2str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }
}