【多维分桶】力扣527-单词缩写

  |  

摘要: 桶外分类、桶内排序

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


各位好,本文我们来看一个分桶的问题。首先根据需求对字符串设计一种哈希值,该值包含了词的长度信息,首字符和尾字符信息。然后依据该值对字符串分桶。对于桶内的字符串,还需要其他的数据结构进行维护。

$1 题目

给定一个由n个不重复非空字符串组成的数组,你需要按照以下规则为每个单词生成最小的缩写。

初始缩写由起始字母+省略字母的数量+结尾字母组成。
若存在冲突,亦即多于一个单词有同样的缩写,则使用更长的前缀代替首字母,直到从单词到缩写的映射唯一。换而言之,最终的缩写必须只能映射到一个单词。
若缩写并不比原单词更短,则保留原样。

注意:

1
2
3
4
n和每个单词的长度均不超过 400。
每个单词的长度大于 1。
单词只由英文小写字母组成。
返回的答案需要和原数组保持同一顺序。

示例:

输入: [“like”, “god”, “internal”, “me”, “internet”, “interval”, “intension”, “face”, “intrusion”]
输出: [“l2e”,”god”,”internal”,”me”,”i6t”,”interval”,”inte4n”,”f2e”,”intr4n”]

$2 题解

算法: 哈希分桶

按照规则,两个词的原始缩写相同的情况:两个词长度相同,且首位字符相同。

因此给每个词计算一个键值 key,该值包含了词的长度信息,首字符和尾字符信息。键值相同的词初始缩写相同,键值不同的词初始缩写不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct MyKey
{
int operator()(const string& s) const
{
int hash = s.size();
int r = s[hash - 1] - 'a';
hash *= 100;
hash += r;
int l = s[0] - 'a';
hash *= 100;
hash += l;
return hash;
}
};

如果按照这种键值将每个词放到相应的桶中。

  • 桶内的词如果只有 1 个,就按初始缩写就好。
  • 但如果桶内的词超过了一个,对于桶内所有词,初始缩写都不行了,就要对桶内所有的单词的缩写进行调整。

对于某个词 w,调整缩写就是要把缩写的前缀加长,于是就要问:桶内其它词与 w 的前缀最长能到多少,记为 prefix_len,有了这一问的答案,调整缩写就有了:

1
w.substr(0, prefix_len) + to_string(len - 1 - prefix_len) + w[len - 1]

为了高效回答这一问,桶内单词需要用数据结构维护。有两种方法:

  • 平衡树: 单词按字典序排序后,对于任意词,与它取到最长公共前缀的总是它的两个相邻词。
  • Trie : 维护桶内每个前缀对应的单词列表。某个节点对应的前缀对应的单词只有一个时,该词的缩写的前缀就用该节点对应的前缀。

数据结构(1): 平衡树(排序)

代码 (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
class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& dict) {
MyKey my_key;
unordered_map<int, map<string, string>> bucket;
for(const string& w: dict)
{
int key = my_key(w);
bucket[key][w] = w;
}
for(auto &b: bucket)
{
adjust(b.second);
}
int n = dict.size();
vector<string> result(n);
for(int i = 0; i < n; ++i)
{
int k = my_key(dict[i]);
result[i] = bucket[k][dict[i]];
}
return result;
}

private:
void adjust(map<string, string>& words)
{
int len = (words.begin() -> first).size();
if(len <= 3) return;
auto it = words.begin();
int prev_prefix_len = 1;
while(it != words.end())
{
const string &w = (it -> first);
int prefix_len = prev_prefix_len;
++it;
if(it != words.end())
{
prev_prefix_len = common_prefix_len(w, it -> first);
prefix_len = max(prefix_len, prev_prefix_len);
}
--it;
if(len - 1 - prefix_len >= 2)
it -> second = w.substr(0, prefix_len) + to_string(len - 1 - prefix_len) + w[len - 1];
++it;
}
}

int common_prefix_len(const string& a, const string& b)
{
int na = a.size(), nb = b.size();
int i = 0;
while(i < na && i < nb && a[i] == b[i])
++i;
return i + 1;
}
};

数据结构(2): Trie

将一个桶内的单词放到一个 trie 中,然后对于每个单词,在其经过的每一个节点(代表某个前缀 P)统计有多少个单词的前缀为 P。如果数目为 1 ,则找到该词应该使用的前缀。

代码 (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
104
105
106
107
108
const int ALPHABETS = 26;

struct TrieNode
{
vector<TrieNode*> children;
int words_cnt; // 具有该节点表示的前缀的字符串的个数
TrieNode()
{
children = vector<TrieNode*>(ALPHABETS, nullptr);
words_cnt = 0;
}
~TrieNode(){}
};

class Trie
{
public:
/** Initialize your data structure here. */
Trie()
{
root = new TrieNode();
}

~Trie()
{
delete_sub_tree(root);
}

void insert(const string& word)
{
TrieNode *iter = root;
for(const char c: word)
{
if(!(iter -> children[_to_int(c)]))
(iter -> children)[_to_int(c)] = new TrieNode();
iter = (iter -> children)[_to_int(c)];
++(iter -> words_cnt);
}
}

int query(const string& s)
{
int deep = find(s);
return deep;
}

private:
TrieNode *root;

void delete_sub_tree(TrieNode *node)
{
for(TrieNode *child: node -> children)
if(child)
delete_sub_tree(child);
delete node;
node = nullptr;
}

int _to_int(char ch) const
{
return ch - 'a';
}

int find(const string& word) const
{
int deep = 0;
const TrieNode* iter = root;
for(const char c: word)
{
if(iter -> words_cnt == 1)
return deep;
iter = (iter -> children)[_to_int(c)];
if(iter == nullptr)
break;
++deep;
}
return -1;
}
};

class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& dict) {
MyKey my_key;
unordered_map<int, Trie*> bucket;
for(const string& w: dict)
{
int key = my_key(w);
if(bucket.count(key) == 0)
bucket[key] = new Trie();
bucket[key] -> insert(w);
}
int n = dict.size();
vector<string> result(n);
for(int i = 0; i < n; ++i)
{
const string &w = dict[i];
int k = my_key(w);
int prefix_len = bucket[k] -> query(w);
int len = w.size();
if(len - 1 - prefix_len >= 2)
result[i] = w.substr(0, prefix_len) + to_string(len - 1 - prefix_len) + w[len - 1];
else
result[i] = w;
}
return result;
}
};

Share