leetcode 290 单词规律

https://leetcode.cn/problems/word-pattern/description/

题目

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

思路

核心思路很简单，就是建立哈希表，key 为 pattern 中的每个规则字母，value 为用空格分别后的每个单词，如果 key 和 value 都不在哈希表中，则添加，如果其中一个在，则查看 key 和 value 是否匹配。

代码

public boolean wordPattern(String pattern, String s) {
	Map<Character, String> map = new HashMap<>();
	String[] words = s.split(" ");

	if (pattern.length() != words.length) {
		return false;
	}

	for (int i = 0; i < words.length; i++) {
		char p = pattern.charAt(i);
		String word = words[i];

		String val = map.get(p);
		if (val == null) {
			if (map.containsValue(word)) {
				return false;
			}
			map.put(p, word);
		} else if (!Objects.equals(word, val)) {
			return false;
		}
	}

	return true;
}

不过需要注意的是，上方 containsValue 方法的时间复杂度是 O (n)，在 leetcode 中还见到一个极其简洁的解法：

class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        if (words.length != pattern.length()) {
            return false;
        }
        Map<Object, Integer> map = new HashMap<>();
        for (Integer i = 0; i < words.length; i++) {
            if (map.put(words[i], i) != map.put(pattern.charAt(i), i)) {
                return false;
            }
        }

        return true;
    }
}

这里利用的是 map.put 方法，如果 key 不存在，插入成功，返回 null；如果 key 存在，返回之前对应的 value。