字符串哈希-字符串同构问题

  |  

摘要: 字符串同构问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


数据结构的同构问题是哈希表解决的一个基本问题,在给定数据结构的同构规则后,如何快速判断两个数据结构是否同构。

对于这种判定同构的问题,哈希方法的做法是对数据结构设计一个哈希函数,比如数组哈希、矩阵哈希、树哈希、图哈希等等。如果两个数据结构的哈希值不同,则肯定不同构,如果哈希值相同,则可能同构,也可能不同构(哈希冲突),此时再用同构规则判断一遍即可。

当数据结构是字符串的时候,就是本文要讨论的字符串同构问题。如果同构规则是完全相等,就是字符串的精确匹配问题。

同构的概念

前面我们提到的数据结构的同构的说法借鉴了近世代数中关于代数结构的同构的概念:

设有两个代数系统 $< A, \ast> $,$< B, \ast> $。如果能在集合 $A$ 和 $B$ 之间构造映射 $f$,并满足以下要求:
(1) $\forall y \in B, \exists x \in A$,使得 $y = f(x)$ (满射)
(2) 当 $x_{1}, x_{2} \in A, x_{1}\neq x_{2}$ 时,有 $f(x_{1}), f(x_{2}) \in B, f(x_{1}) \neq f(x_{2})$ (单射)
(3) $\forall x_{1}, x_{2}\in A$,有 $f(x_{1} \ast x_{2}) = f(x_{1}) \ast f(x_{2})$
则称两个代数系统的结构相同,简称同构,记为 $< A, \ast> \cong < B, \ast> $,$f$ 为同构映射。

如果代数结构是群,那么就是我们比较熟悉的群的同构的概念:

设 $G$ 和 $G’$ 是两个群,如果 $G$ 到 $G’$ 有一个双射 $\sigma$,使得:
$\forall a, b \in G$,有 $\sigma(ab) = \sigma(a)\sigma(b)$
则称群 $G$ 和 $G’$ 是同构的,记为 $G \cong G’$,称 $\sigma$ 是 $G$ 到 $G’$ 的同构映射。


题目

题目 205. 同构字符串 是给定同构的规则,判断 2 个字符串是否同构,这种就判断一次的问题,可以直接按照规则对比。下面这个问题是从单词列表中找出所有与模式串同构的单词,这就需要用到字符串哈希了。


你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。

如果存在字母的排列 p ,使得将模式中的每个字母 x 替换为 p(x) 之后,我们就得到了所需的单词,那么单词与模式是匹配的。

(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)

返回 words 中与给定模式匹配的单词列表。

你可以按任何顺序返回答案。

提示:

1
2
1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20

示例:
输入:words = [“abc”,”deq”,”mee”,”aqq”,”dkd”,”ccc”], pattern = “abb”
输出:[“mee”,”aqq”]
解释:
“mee” 与模式匹配,因为存在排列 {a -> m, b -> e, …}。
“ccc” 与模式不匹配,因为 {a -> c, b -> c, …} 不是排列。
因为 a 和 b 映射到同一个字母。

题解

算法:字符串哈希

  • 从 words 中找到所有与 p 同构的单词。

对 s 求哈希函数时,先将其中每个字符根据某种规则(也就是前面提到的同构映射的概念)映射到另一字符,再代入哈希函数的公式

代码中的 get_mapping 就是在确定一个这样的映射规则。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
string new_p = get_mapping(pattern);
vector<string> result;
for(const string& s: words)
{
string new_s = get_mapping(s);
if(new_s == new_p)
result.push_back(s);
}
return result;
}

private:
unordered_map<char, char> mapping;

string get_mapping(const string& s)
{
mapping.clear();
char iter = 'a';
for(const char& ch: s)
{
if(mapping.count(ch) > 0)
continue;
mapping[ch] = iter++;
}
string result = s;
for(char &ch: result)
ch = mapping[ch];
return result;
}
};

Share