如何在数字字符串中识别平方序列并完成剔除操作

功能说明 #

• 输入：纯数字组成的字符串
• 处理规则：识别字符串中所有连续组成完全平方数的子串并剔除，保留未匹配的剩余字符
• 参考示例：输入1232416256789，处理后输出为123789

核心实现思路 #

为了避免短平方数匹配后破坏长平方数的匹配结果，采用贪心最长匹配规则：

1. 预先生成所有长度不超过输入字符串长度的完全平方数，转成字符串存入集合
2. 将所有平方数字符串按长度倒序排列，匹配时优先尝试更长的串
3. 从字符串起始位置开始遍历，匹配到平方数则跳过对应长度的字符，未匹配到则将当前字符存入结果，向后移动一位继续遍历

Python 实现代码 #

def remove_square_substrings(input_str: str) -> str:
    # 预生成所有符合长度要求的平方数字符串
    max_possible_len = len(input_str)
    square_str_set = set()
    num = 0
    while True:
        square = num * num
        square_str = str(square)
        str_len = len(square_str)
        if str_len > max_possible_len:
            break
        square_str_set.add(square_str)
        num += 1
    # 按长度倒序，优先匹配更长的平方数
    sorted_squares = sorted(square_str_set, key=lambda x: -len(x))
    
    result = []
    current_pos = 0
    str_total_len = len(input_str)
    while current_pos < str_total_len:
        is_matched = False
        for sq_str in sorted_squares:
            sq_len = len(sq_str)
            # 剩余长度不足时跳过当前平方数
            if current_pos + sq_len > str_total_len:
                continue
            if input_str[current_pos:current_pos+sq_len] == sq_str:
                current_pos += sq_len
                is_matched = True
                break
        if not is_matched:
            result.append(input_str[current_pos])
            current_pos += 1
    return ''.join(result)

# 示例测试
if __name__ == "__main__":
    test_input = "1232416256789"
    print(remove_square_substrings(test_input)) # 输出：123789

内容的提问来源于stack exchange，提问作者Muthukumaran G