290. 单词规律

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"

Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"

Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"

Output: false

Constraints:

• 1 <= pattern.length <= 300
• pattern contains only lower-case English letters.
• 1 <= s.length <= 3000
• s contains only lowercase English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.

题目大意

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

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

解题思路

为了判断字符串是否遵循相同的规律，可以使用两个哈希表 map1 和 map2 来分别建立字符到单词和单词到字符的映射关系。具体的思路如下：

1. 分割字符串：首先，将输入的字符串 str 使用空格分割成一个单词数组。

2. 建立映射关系：对于规律字符串 pattern 和单词数组，同时遍历它们的每个元素。对于 pattern[i] 和 arr[i]，如果 pattern[i] 已经在 map1 中，但对应的值不等于 arr[i]，说明不满足规律，返回 false；如果 pattern[i] 不在 map1 中，但 arr[i] 在 map2 中，说明不满足规律，返回 false。如果都符合条件，则建立映射关系。

3. 返回结果：遍历结束后，如果没有发现不满足规律的情况，说明字符串满足相同的规律，返回 true。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。
• 空间复杂度：O(k)，其中 k 是字符集的大小，通常是常数大小。

代码

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
var wordPattern = function (pattern, s) {
	const arr = s.split(' ');
	if (arr.length !== pattern.length) {
		return false;
	}
	let map1 = new Map();
	let map2 = new Map();

	for (let i in pattern) {
		if (!map1.has(pattern[i])) {
			map1.set(pattern[i], arr[i]);
		} else if (map1.get(pattern[i]) !== arr[i]) {
			return false;
		}

		if (!map2.has(arr[i])) {
			map2.set(arr[i], pattern[i]);
		} else if (map2.get(arr[i]) !== pattern[i]) {
			return false;
		}
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度
205	同构字符串	[✓]	哈希表 字符串
291	单词规律 II 🔒		哈希表 字符串 回溯
890	查找和替换模式		数组 哈希表 字符串