算法字符串

字符串同构问题：最小表示法与哈希表

字数统计: 3.5k字   |   阅读时长: 14分
, , ,

摘要: 字符串同构问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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’$ 的同构映射。

判定两个对象是否同构的思路

数据结构的同构问题是指，在给定数据结构的同构规则后，如何快速判断两个数据结构是否同构。

如何用同构的规则判断两个对象是否同构，有时并不简单。在同一个同构类中的对象，如果能定义某种大小比较的方法，使得同构类中有一个最小的对象，称为最小表示法。各个对象都可以比较方便地转换为最小的对象，那么在比较对象 a 和 b 的时候，就可以先将 a 和 b 分别转换为其同构类中的最小对象，然后看 a 和 b 所得的最小对象是否完全相等即可。

当对象规模为 $N$ 时，最小表示法的时间复杂度一般为 $O(N)$。

给定一组对象找出其中的同构

对于判断两个对象是否同构的问题。直接用最小表示法解决即可，这是一对一的问题。但如果是多对多的问题，比如给定 $M$ 个对象，问其中有哪些是同构的，就没那么简单了。

一种直接的思路是，枚举其中所有的元素对 $(a, b)$，用最小表示法判定其是否同构。这样元素对有 $O(M^{2})$ 个，最小表示法判定需要 $O(N)$，总体需要 $O(NM^{2})$ 时间复杂度。

哈希方法的做法是给对象设计一个哈希函数，根据数据结构的不同会有不同的设计方法，比如数组哈希、矩阵哈希、树哈希、图哈希等等。设计原则是如果对象规模为 $N$，则哈希值计算的时间复杂度为 $O(N)$，并且如果两个数据结构的哈希值不同，则肯定不同构，如果哈希值相同，则可能同构，也可能不同构（哈希冲突），此时再用同构规则判断一遍即可。

这样的话，可以维护一个哈希表，键是对象的哈希值，值为保存相同哈希值的对象的数组。依次枚举 $M$ 个对象，先以 $O(N)$ 计算其哈希值 h，然后枚举 mapping 中所有哈希值为 h 的对象，以 $O(N)$ 进行最小表示法判定。在最坏的情况下，当所有对象的哈希值均相同时，时间复杂度为 $O(NM^{2})$，但这是极小概率。平均情况的时间复杂度低于 $O(NM^{2})$，这是哈希表的高效检索特性带来的提升。

对于一对多的问题，如果规模为 N 的对象用最小表示法判定以及求哈希值的时间复杂度相同（比如都是 $O(N)$）则，使用哈希方法的提升并不大。

当数据结构是字符串的时候，就是本文要讨论的字符串同构问题。如果同构规则是完全相等，就是字符串的精确匹配问题。下面看几个字符串同构方面的题目。

同构规则：字符一一映射

205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:
输入：s = “egg”, t = “add”
输出：true

示例 2：
输入：s = “foo”, t = “bar”
输出：false

示例 3：
输入：s = “paper”, t = “title”
输出：true

提示：

1
2
3
1 <= s.length <= 5e4
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

算法：最小表示法

同构规则是，如果存在一种字符之间的一一映射，使得 s 映射后的字符串为 t，那么 s 和 t 同构。

对于字符串 s，按顺序枚举其字符，构造一个映射 mapping，以及当前的最小可用字符 ch，并维护最小表示法 t。对于字符 s[i]，首先处理映射表：

  • 如果它在 mapping 中是第一次出现，那么将其映射为 ch，即 mapping[s[i]] = ch，然后将 ch 自增 1；
  • 如果它在 mapping 中出现过，则不更新 mapping。

处理完映射表后，记录最小表示法相应位置字符，即 t[i] = mapping[s[i]]。

代码(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
string get_min_representation(string& s)
{
    int n = s.size();
    char ch = 'a';
    string t = s;
    unordered_map<char, char> mapping;
    for(int i = 0; i < n; ++i)
    {
        if(mapping.count(s[i]) == 0)
        {
            mapping[s[i]] = ch;
            ch++;
        }
        t[i] = mapping[s[i]];
    }
    return t;
}

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        return get_min_representation(s) == get_min_representation(t);
    }
};

890. 查找和替换模式

你有一个单词列表 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 映射到同一个字母。

算法：最小表示法

同构规则是，如果存在一种字符之间的一一映射，使得 s 映射后的字符串为 t，那么 s 和 t 同构。与上一题一样。

上一题是给定同构的规则，判断 2 个字符串是否同构，这种就判断一次的问题，可以直接按照规则对比，具体是用最小表示法，时间复杂度 $O(N)$。

本题从单词列表中找出所有与模式串同构的单词，最直接的做法是枚举单词列表的每个词 s，将其与模式串 p 用最小表示法进行对比，判断是否同构。则时间复杂度为 $O(MN)$，其中 $M$ 为列表长度，$N$ 为字符串长度。

如果用哈希方法，由于算哈希值也需要 $O(N)$，M 个字符串的哈希值算完也就要 $O(MN)$，时间复杂度没有提升。因此只要最小表示法的时间复杂度与算哈希值相同，这种一对多的同构判定就直接用最小表示法即可。

代码 (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
string get_min_representation(const string& s)
{
    int n = s.size();
    char ch = 'a';
    string t = s;
    unordered_map<char, char> mapping;
    for(int i = 0; i < n; ++i)
    {
        if(mapping.count(s[i]) == 0)
        {
            mapping[s[i]] = ch;
            ch++;
        }
        t[i] = mapping[s[i]];
    }
    return t;
}


class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        string p_min = get_min_representation(pattern);
        vector<string> result;
        for(const string& s: words)
        {
            string s_min = get_min_representation(s);
            if(s_min == p_min)
                result.push_back(s);
        }
        return result;
    }
};

同构规则：循环移位或翻转

有 N 片雪花，每片雪花由六个角组成，每个角都有长度。

第 i 片雪花六个角的长度从某个角开始顺时针依次记为 $a_{i,1},a_{i,2},\cdots,a_{i,6}$。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

例如 $a_{i,1},a_{i,2},\cdots,a_{i,6}$ 和 $a_{i,2},a_{i,3},\cdot,a_{i,6}，a_{i,1}$ 就是形状相同的雪花。

$a_{i,1},a_{i,2},\cdots,a_{i,6}$ 和 $a_{i,6},a_{i,5},\cdots,a_{i,1}$ 也是形状相同的雪花。

我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。

求这 N 片雪花中是否存在两片形状相同的雪花。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入格式
第一行输入一个整数 N，代表雪花的数量。
接下来 N 行，每行描述一片雪花。
每行包含 6 个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。
同行数值之间，用空格隔开。

输出格式
如果不存在两片形状相同的雪花，则输出：
No two snowflakes are alike.
如果存在两片形状相同的雪花，则输出：
Twin snowflakes found.

数据范围
1<=N<=100000,
0<=ai,j<10000000

输入样例：
2
1 2 3 4 5 6
4 3 2 1 6 5
输出样例：
Twin snowflakes found.

算法：哈希表 + 最小表示法

两片雪花同构的规则是：若雪花 1 翻转后，或者循环移位后与雪花 2 相同，则雪花 1 和雪花 2 相同。

定义哈希函数的原则是当两个雪花同构的时候，哈希值必须相同，当雪花不同构的时候，哈希值相同的概率尽量小。

按照上述同构规则，两片同构的雪花，其 6 个角的乘积与和都相同。写出以下哈希函数：

建立一个哈希映射 mapping，键为雪花的哈希值，值为一个链表，其中保存相同哈希值的雪花。枚举每个雪花，计算其哈希值 h，若哈希值在 mapping 中已经存在，则遍历 mapping[h] 中的每个雪花，与当前雪花执行一次对比，判断是否相同。

当哈希值相同时，对比两片雪花是否循环同构，可以 $O(N)$ 的时间复杂度通过最小表示法来判断，由于翻转后循环同构也是算的，因此取第一个雪花翻转之后的最小表示法再对比一次即可。最小表示法的原理与代码模板，可以参考 字符串的循环同构与最小表示法。

在平均情况下时间复杂度为 $O(N^{2}/P)$，当 $P$ 为接近 $N$ 的质数，则平均时间复杂度接近 $O(N)$。

代码 (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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
const int P = 99991;

int H(const vector<int>& a)
{
    int ans1 = 0;
    int ans2 = 1;
    for(int j = 0; j < 6; ++j)
    {
        ans1 = ((ll)ans1 + a[j]) % P;
        ans2 = ((ll)ans2 * a[j]) % P;
    }
    return ((ll)ans1 + ans2) % P;
}

int get_min_representation(const vector<int>& s)
{
    int N = s.size();
    int i = 0, j = 1;
    while(i < N && j < N)
    {
        int k = 0;
        while(k < N && s[(i + k) % N] == s[(j + k) % N])
            k++;
        if(k == N)
            break;
        if(s[(i + k) % N] < s[(j + k) % N])
        {
            j += k + 1;
            if(i == j)
                j++;
        }
        else
        {
            i += k + 1;
            if(i == j)
                i++;
        }
    }
    return min(i, j);
}

bool equal(const vector<int>& a1, const vector<int>& a2, int min1, int min2)
{
    for(int k = 0; k < 6; ++k)
    {
        if(a1[(min1 + k) % 6] != a2[(min2 + k) % 6])
            return false;
    }
    return true;
}

bool check(vector<int>& a1, const vector<int>& a2)
{
    // 最小表示法比较 a1 与 a2 是否同构
    reverse(a1.begin(), a1.end());
    int min1_reversed = get_min_representation(a1);
    int min2 = get_min_representation(a2);
    if(equal(a1, a2, min1_reversed, min2))
        return true;
    reverse(a1.begin(), a1.end());
    int min1 = get_min_representation(a1);
    if(equal(a1, a2, min1, min2))
        return true;
    return false;
}

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> a(N, vector<int>(6));
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < 6; ++j)
            cin >> a[i][j];
    }
    unordered_map<int, vector<vector<int>>> mapping;
    for(int i = 0; i < N; ++i)
    {
        int h = H(a[i]);
        if(mapping.count(h) > 0)
        {
            for(vector<int>& item: mapping[h])
            {
                if(check(item, a[i]))
                {
                    cout << "Twin snowflakes found." << endl;
                    return 0;
                }
            }
        }
        mapping[h].push_back(a[i]);
    }
    cout << "No two snowflakes are alike." << endl;
}
Share