如何优化字母映射数字构造最大无重复数位平方数的算法以支持更长字符串

问题需求 #

给定由互不重复字母组成的字符串，需将每个字母映射为唯一数字，最终拼接得到的数字需同时满足以下条件：

• 是所有可行结果中最大的数
• 所有数位互不重复
• 是平方数

参考示例 #

• 字符串care映射规则：c→9，a→8，r→0，e→1，对应平方数9801
• 字符串habit映射规则：h→9，a→6，b→7，i→2，t→1，对应平方数96721

原有实现及问题 #

原有代码 #

from math import sqrt

def sqr(n):
  i = int(sqrt(n))**2
  if len(set(str(i))) == len(str(i)):
    return i
  else:
    return sqr(i-1)

s = input()
n = 10**len(s)
r = sqr(n)

for i,j in zip(s,str(r)): 
  print(i,j)

现存缺陷 #

• 处理长度≤8的字符串时耗时3-4秒，性能较差
• 处理更长字符串时会抛出递归深度超限错误：
  RecursionError: maximum recursion depth exceeded while getting the str of an object

优化解决方案 #

问题根因 #

原有递归实现每次仅减1遍历候选值，递归深度随需要跳过的不符合要求的数的数量线性增长，不仅重复计算平方根拉高耗时，还很容易超过Python默认的1000层递归深度上限。

优化思路 #

1. 替换递归为迭代循环，从最大的候选平方根开始向下遍历，直接计算平方验证，完全规避栈溢出风险
2. 省去重复的平方根计算步骤，直接从int(sqrt(10**字符串长度))开始递减遍历，验证成本大幅降低
3. 增加长度预判逻辑，长度不匹配的结果直接跳过，进一步减少无效计算

优化后代码 #

from math import sqrt

def get_max_unique_square(str_len):
    # 取对应长度最大数的平方根作为遍历起点
    max_root = int(sqrt(10 ** str_len - 1))
    for root in range(max_root, 0, -1):
        square = root * root
        square_str = str(square)
        # 长度不匹配直接跳过
        if len(square_str) != str_len:
            continue
        # 验证数位无重复
        if len(set(square_str)) == str_len:
            return square_str
    return ""

if __name__ == "__main__":
    input_str = input().strip()
    str_len = len(input_str)
    target_square = get_max_unique_square(str_len)
    for char, digit in zip(input_str, target_square):
        print(char, digit)

优化效果 #

• 无递归深度限制，支持最长10位的字符串（0-9共10个唯一数字，最长无重复数位的数为10位）
• 性能提升显著，长度8的字符串处理耗时从3-4秒降低到毫秒级

内容的提问来源于stack exchange，提问作者Vidhi Shah