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