• 字典序问题


    字典序问题

    问题描述

    数据加密和数据压缩中常需要对特殊的字符串进行编码。

    • 给定的字母表A26小写英文字母组成A={a,b, .. z}
    • 该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同,且每个字符最多出现1
    • 例如,a, b, ab, bc, xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升字符串按照字典序排列并编码如下
      在这里插入图片描述

    简而言之,就是对字符串进行了编码,其中a -> 0b -> 1,…, z -> 26,而ab ->27, …, az -> 52,但是

    az的下一个不是ba,因为字符串要求升序

    az的下一个也不是bb,因为字符串要求不重复

    az的下一个是bc

    思路

    1. 将所有符合规则的字符串存入数组

    2. 再用一个哈希表来记录数组中所有字符串对应的编码,这样查询时只需要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是前缀的后一个字符(若前缀为abch='c'

    代码

    python

    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
    
    • 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

    测试

    print(
        book['xy'],
        book['a'],
        book['ab'],
        book['az']
    )
    
    """
    349 1 27 51
    """
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
  • 相关阅读:
    UnionFind(并查集)
    云原生架构体系
    STM32单片机PID控制数控恒流源-100mA~+100mA输出正负恒流源
    【愚公系列】2022年11月 .NET CORE工具案例-.NET Core执行JavaScript
    cv::Mat类的矩阵内容输出的各种格式的例子
    【Verilog基础】【计算机体系结构】多核cache一致性
    CSS 常用样式 之字体属性
    UVA220 黑白棋 Othello
    ubuntu 22.04版本修改时区的操作方法
    通过Python的speech_recognition库将音频文件转为文字
  • 原文地址:https://blog.csdn.net/m0_52733659/article/details/126663248