如何实现按字典序为字符串分配唯一整数值的get_key函数

有两种常用的实现思路，分别适配不同的使用场景：

方案1：全局缓存间隙分配法（通用场景，无字符集/长度限制） #

核心思路 #

维护全局的字符串-key映射表和有序字符串列表，每次遇到新字符串时，在它前后两个已有字符串的key间隙中分配新的key，保证key的大小顺序和字符串字典序完全一致。如果间隙不足，就将所有已分配的key整体放大2倍，既不改变原有大小顺序，也能腾出足够的新间隙。

优势 #

• 支持任意字符集、任意长度的字符串，不需要预先设置任何边界条件
• 同一个字符串的返回值永久固定
• 整数比较完全是O(1)时间复杂度

代码实现 #

import bisect

# 全局状态维护
_key_map = {}
_sorted_pairs = []  # 按字符串字典序排序的(字符串, 对应key)元组列表
_INIT_LEFT = 0
_INIT_RIGHT = 1 << 128  # 初始右边界，Python支持任意大整数可按需扩展

def get_key(s: str) -> int:
    global _INIT_LEFT, _INIT_RIGHT
    # 已分配过的key直接返回
    if s in _key_map:
        return _key_map[s]
    
    # 查找新字符串的插入位置
    pos = bisect.bisect_left(_sorted_pairs, (s, 0))
    
    # 确定新key的左右边界
    if pos == 0:
        left_k = _INIT_LEFT
        right_k = _sorted_pairs[0][1] if _sorted_pairs else _INIT_RIGHT
    elif pos == len(_sorted_pairs):
        left_k = _sorted_pairs[-1][1]
        right_k = _INIT_RIGHT
    else:
        left_k = _sorted_pairs[pos-1][1]
        right_k = _sorted_pairs[pos][1]
    
    # 间隙不足时整体放大所有key，不改变原有大小顺序
    if right_k - left_k <= 1:
        _INIT_LEFT <<= 1
        _INIT_RIGHT <<= 1
        for i in range(len(_sorted_pairs)):
            old_s, old_k = _sorted_pairs[i]
            new_k = old_k << 1
            _sorted_pairs[i] = (old_s, new_k)
            _key_map[old_s] = new_k
        left_k <<= 1
        right_k <<= 1
    
    # 分配新key并存入缓存
    new_k = (left_k + right_k) // 2
    _key_map[s] = new_k
    bisect.insort(_sorted_pairs, (s, new_k))
    return new_k

测试示例 #

print(get_key('aaa') < get_key('b'))  # 输出 True
print(get_key('a') < get_key('aaa'))  # 输出 True
print(get_key('z') > get_key('bbbb')) # 输出 True

方案2：固定基数权重法（适合已知字符串最大长度的场景） #

核心思路 #

如果业务场景可以预先确定字符串的最大长度N，我们可以给每个位置的字符设置足够高的权重，保证左侧字符的权重永远高于右侧所有字符的总和。以小写字母为例，选择27作为基数（对应a-z的1-26，预留0作为空占位），第i位（从左到右从0开始计数）的权重为27 ** (N - i)，即可保证字典序高的字符串对应的整数值一定更大。

优势 #

• 不需要维护全局缓存，无副作用
• 逻辑简单，计算速度快

代码实现（假设最大字符串长度为20） #

# 可根据业务实际最大长度调整MAX_LEN
MAX_LEN = 20
BASE = 27

def get_key(s: str) -> int:
    if len(s) > MAX_LEN:
        raise ValueError(f"字符串长度不能超过{MAX_LEN}")
    key = 0
    for i, c in enumerate(s):
        # 字符映射为1-26，避免0值导致权重失效
        char_val = ord(c) - ord('a') + 1
        weight = BASE ** (MAX_LEN - i)
        key += char_val * weight
    return key

测试示例 #

print(get_key('aaa') < get_key('b'))  # 输出 True
print(get_key('a') < get_key('aaa'))  # 输出 True

内容的提问来源于stack exchange，提问作者Roy Fischer