290. Word Pattern

290. Word Patternopen in new window

🟢 🔖 哈希表 字符串 🔗 LeetCodeopen in new window

题目

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 来分别建立字符到单词和单词到字符的映射关系。具体的思路如下：

分割字符串：首先，将输入的字符串 str 使用空格分割成一个单词数组。
建立映射关系：对于规律字符串 pattern 和单词数组，同时遍历它们的每个元素。对于 pattern[i] 和 arr[i]，如果 pattern[i] 已经在 map1 中，但对应的值不等于 arr[i]，说明不满足规律，返回 false；如果 pattern[i] 不在 map1 中，但 arr[i] 在 map2 中，说明不满足规律，返回 false。如果都符合条件，则建立映射关系。
返回结果：遍历结束后，如果没有发现不满足规律的情况，说明字符串满足相同的规律，返回 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;
};

290. Word Pattern

# 290. Word Patternopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

290. Word Patternopen in new window

题目

题目大意

解题思路

代码

相关题目