网站建设2000字论文,信息网络安全,网页源代码是什么,电商公司的网上设计给定一种规律 pattern 和一个字符串 s #xff0c;判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配#xff0c;例如#xff0c; pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
#include string
#include unordered_ma…给定一种规律 pattern 和一个字符串 s 判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配例如 pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
#include string
#include unordered_map
#include sstreamusing namespace std;class Solution {
public:bool wordPattern(string pattern, string s) {unordered_mapchar, string charToWord;unordered_mapstring, char wordToChar;istringstream ss(s);string word;for (char c : pattern) {if (!(ss word)) // 如果没有更多单词了返回 falsereturn false;// 如果当前字符已经在哈希表中检查是否对应的单词匹配if (charToWord.find(c) ! charToWord.end()) {if (charToWord[c] ! word)return false;} else {// 如果当前单词已经在哈希表中检查是否对应的字符匹配if (wordToChar.find(word) ! wordToChar.end()) {if (wordToChar[word] ! c)return false;} else {// 如果当前字符和单词都不在哈希表中进行映射charToWord[c] word;wordToChar[word] c;}}}// 检查是否还有多余的单词return !(ss word);}
};
遍历 pattern 中的每个字符同时使用istringstream从字符串 s 中提取单词。在遍历过程中建立字符到单词的映射和单词到字符的映射并检查映射是否正确。如果遍历完 pattern 后仍然存在未匹配的单词则返回 false。
时间复杂度分析 这个算法的时间复杂度取决于字符串 s 中单词的数量和 pattern 的长度设 n 为 s 中单词的数量m 为 pattern 的长度
遍历 pattern 的过程中需要将每个字符映射到对应的单词这需要 O(m) 的时间复杂度。 使用istringstream从字符串 s 中提取单词的过程中需要 O(n) 的时间复杂度。 最后检查是否还有多余的单词需要 O(1) 的时间复杂度。 因此总的时间复杂度为 O(m n)。
空间复杂度分析 空间复杂度主要取决于哈希表的存储哈希表的大小取决于 pattern 中唯一字符的数量和 s 中单词的数量
哈希表 charToWord 存储了 pattern 中的每个字符到对应的单词空间复杂度为 O(字符集大小)。 哈希表 wordToChar 存储了 s 中的每个单词到对应的字符空间复杂度也为 O(单词数量)。 因此总的空间复杂度为 O(字符集大小 单词数量)。
