0290. Word Pattern
=================
题目信息
--------
:题号: 0290
:难度: Easy
:主题: 字符串、单词序列、双射映射
:原题: `LeetCode 0290 `_
:重点: 模式字符与单词必须一一对应、相同字符映射相同单词、不同字符不能共享单词、数量必须一致
题目重述
--------
给定只包含小写英文字母的模式串 ``pattern``,以及由若干小写英文单词组成的字符串 ``s``。``s`` 中相邻单词由一个空格分隔,并且没有前导或尾随空格。判断单词序列是否完全遵循模式串。
所谓遵循模式,是指模式字符与单词之间存在双射:同一个模式字符在每次出现时必须对应同一个单词;两个不同模式字符不能对应同一个单词;同时单词数量必须恰好等于 ``pattern`` 的字符数量,不能有多余或缺失。
``pattern`` 的长度位于 ``[1, 300]``,``s`` 的长度位于 ``[1, 3000]``,其中的单词只包含小写英文字母。函数只返回布尔结果,不需要返回具体映射。
自建示例
--------
双向对应成立:
.. code-block:: text
输入:pattern = "abba",s = "red blue blue red"
输出:true
解释:a 始终对应 red,b 始终对应 blue,并且两个字符没有映射到同一个单词。
不同字符错误地共享单词:
.. code-block:: text
输入:pattern = "ab",s = "same same"
输出:false
解释:a 和 b 是不同字符,却都对应 same,违反一一对应关系。
数量不一致:
.. code-block:: text
输入:pattern = "abc",s = "one two"
输出:false
解释:模式有三个字符,但字符串只有两个单词,无法逐项建立映射。
字符与单词的双向映射
--------------------
先按空格解析出单词序列,并检查单词数是否等于 ``pattern`` 长度。随后同步扫描:
.. code-block:: text
pattern_to_word[pattern[i]] = words[i]
word_to_pattern[words[i]] = pattern[i]
同一方向的旧映射必须一致,反方向也必须一致;只有两个方向都没有冲突时才登记新配对。
只维护字符到单词的单向表会错误接受 ``ab`` 与 ``same same``,所以反向表不可省略。
正确性说明
----------
单词数量相等保证每个模式位置都有且只有一个对应位置。扫描前缀时,两个映射表记录的正是此前所有配对;
若发现源字符对应不同单词或不同字符共享一个单词,任何双射都不可能满足,返回假;
否则加入的新配对保持双向唯一性。扫描结束时所有位置都满足同一映射,因而返回真当且仅当存在合法双射。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
bool wordPattern(const std::string& pattern, const std::string& s) {
std::istringstream input(s);
std::vector words;
std::string word;
while (input >> word) words.push_back(word);
if (words.size() != pattern.size()) return false;
std::unordered_map pattern_to_word;
std::unordered_map word_to_pattern;
for (int i = 0; i < static_cast(pattern.size()); ++i) {
const char letter = pattern[i];
const std::string& current = words[i];
auto pattern_it = pattern_to_word.find(letter);
if (pattern_it != pattern_to_word.end() &&
pattern_it->second != current) return false;
auto word_it = word_to_pattern.find(current);
if (word_it != word_to_pattern.end() &&
word_it->second != letter) return false;
pattern_to_word[letter] = current;
word_to_pattern[current] = letter;
}
return true;
}
};
代码分析
--------
解析字符串和映射扫描均为线性;哈希表平均时间复杂度为 ``O(|s|)``,额外空间为不同单词数和模式字符数之和。
``istringstream`` 按空格提取单词,符合题目没有前导、尾随和重复分隔空格的输入合同;输入字符串不被修改。