在数据加密和数据压缩中常需要对特殊的字符串进行编码。
A
由26
个小写英文字母组成A={a,b, .. z}
1
次a, b, ab, bc, xyz
等字符串都是升序字符串。现在对字母表A
产生的所有长度不超过6
的升字符串按照字典序排列并编码如下简而言之,就是对字符串进行了编码,其中
a -> 0
,b -> 1
,…,z -> 26
,而ab ->27
, …,az -> 52
,但是
az
的下一个不是ba
,因为字符串要求升序
az
的下一个也不是bb
,因为字符串要求不重复
az
的下一个是bc
将所有符合规则的字符串存入数组
再用一个哈希表来记录数组中所有字符串对应的编码,这样查询时只需要O(1)
的时间
可以用数组v
的下标来表示字符串的长度,例如v[0]
表示长度为1
当字符串长度为1
时
数组中存入a~z
v[0] = ['a', 'b', 'c', 'd', 'e', 'f', 'g', ..., 'z']
当字符串长度为2
时
数组中存入ab ~ yz
v[1] = [ 'ab', 'ac', 'ad', ..., 'xy', 'xz', 'yz' ]
当字符串长度为3
时,第一个字符串为abc
,…
只要观察长度1、2的关系,就能推导出来
长度为2
以a
开头的字符串,取的是v[0]
的v[0][1] ~ v[0][25]
,即b~z
以b
开头的字符串,取的是v[0]
的v[0][2] ~ v[0][25]
,即c~z
…
长度为3
以a
开头的字符串,取的是ab + c~z
,其中ab是v[1][0]
规律就是,长度为n
的字符串,以长度为n-1
的字符串为前缀,再加上ch ~ z
,其中ch是前缀的后一个字符(若前缀为ab
,ch='c'
)
book_size = 6 + 1 # 最长的字符串个数为 6, +1是因为 数组不要0位置
v = [None] * book_size # 声明数组
v[1] = [chr(i) for i in range(97, 97+26)] # 所有长度为 1 的字符串
# 将长度为 2 ~ (book_size - 1) 的字符串全部存入 v
for i in range(2, book_size):
len1 = len(v[i-1]) # 长度为 i-1 的字符串有多少个
# 遍历所有长度为 i-1 的字符串
for j in range(len1):
tmp = v[i-1][j] # 其中的一个字符串,例如 ab
key = chr( ord(tmp[len(tmp)-1]) + 1) # tmp 最后一个字符的下一个字符,比如 c
# 如果 v[i] 是 None,就创建一个
# 必须判断,比如 [] 经过一轮循环后是 ['ab', 'ac', 'az']
# 下一轮循环就不用创建了,如果创建了,反而会刷新掉 ['ab', 'ac', 'az']
if v[i] is
v[i] = list()
# 将前缀和后一个字符叠加起来,加入数组,例如 ab + c = abc
while key <= 'z':
v[i].append("".join(tmp + key))
key = chr(ord(key) + 1)
# 编码
cur = 1
book = dict()
for i in range(1, book_size):
# 轮流给字符串赋值
for s in v[i]:
book[s] = cur
cur += 1
测试
print(
book['xy'],
book['a'],
book['ab'],
book['az']
)
"""
349 1 27 51
"""