look_and_say()函数逆向实现方案求助及代码问题排查

我需要实现一个look-and-say函数的逆向函数：输入数字字符串，返回所有能生成该字符串的look-and-say输入列表。规则是：目标数字必须是1位，计数长度可变，不能出现类似"37次54"的情况（因为54是两位数字）。例如输入"3754"，预期输出是["77744444", "444...444"]（后者是375个4）。

当前用迭代+HashMap去重的方案，但输入"3754"时，输出无法正确拼接"777"和"44444"，附上现有Kotlin代码，求修正方向。

fun sayAndCount(
    string: String,
    counts: MutableList<String> = mutableListOf(),
    memory: HashMap<String, String> = HashMap(),
): List<String> {

    if (memory.containsKey(string)) {
       return listOf()
    }

    val times =  string.substring(0, string.lastIndex)
    val number = string.last()
    val count = number.toString().repeat(times.toInt())
    memory[string] = count

    if (string.length <= 3) {
        return listOf(count)
    }

    for (index in 2 until string.lastIndex) {
        counts.addAll(sayAndCount(string.substring(0, index), counts, memory))
        counts.addAll(sayAndCount(string.substring(index), counts, memory))
    }

    return counts.toList()
}

问题分析 #

现有代码的核心逻辑存在以下问题：

1. 拆分结果未拼接：拆分字符串后，仅将左右部分的解析结果分别加入列表，没有将左结果和右结果两两拼接，导致无法生成"777"+"44444"这类组合。
2. 缓存逻辑错误：当字符串已在缓存中时直接返回空列表，丢失了已计算的有效结果，应该返回缓存中存储的解析结果。
3. 拆分范围遗漏：2 until string.lastIndex的循环范围会跳过部分合法拆分点，导致无法覆盖所有可能的组合情况。
4. 终止条件不严谨：未校验次数的合法性（比如次数不能为0），存在无效解析的风险。

修正方案与代码 #

修正后的代码需要覆盖两种核心场景：将当前字符串作为整体解析，或拆分为左右两部分解析后拼接结果，同时通过缓存避免重复计算，最后对结果去重。

fun reverseLookAndSay(input: String): List<String> {
    val memory = mutableMapOf<String, List<String>>()

    fun helper(s: String): List<String> {
        // 缓存命中直接返回
        if (memory.containsKey(s)) {
            return memory[s]!!
        }

        val results = mutableListOf<String>()

        // 场景1：将当前字符串作为整体解析（前len-1位为次数，最后一位为目标数字）
        if (s.length >= 2) {
            val timesStr = s.substring(0, s.lastIndex)
            val digit = s.last()
            // 确保次数为有效正整数
            runCatching {
                val times = timesStr.toInt()
                if (times > 0) {
                    results.add(digit.toString().repeat(times))
                }
            }
        }

        // 场景2：拆分字符串为左右两部分，分别解析后拼接所有组合
        // 拆分点需保证左右部分都能独立解析（长度至少为2）
        for (splitIndex in 2..s.length - 2) {
            val leftPart = s.substring(0, splitIndex)
            val rightPart = s.substring(splitIndex)
            val leftResults = helper(leftPart)
            val rightResults = helper(rightPart)
            // 两两拼接左右结果
            leftResults.forEach { left ->
                rightResults.forEach { right ->
                    results.add(left + right)
                }
            }
        }

        // 去重后存入缓存
        val uniqueResults = results.distinct()
        memory[s] = uniqueResults
        return uniqueResults
    }

    return helper(input)
}

测试验证 #

调用reverseLookAndSay("3754")会返回预期结果：

• "77744444"：由"37"解析为3次7、"54"解析为5次4拼接而来
• "4".repeat(375)：由"3754"整体解析为375次4而来

内容的提问来源于stack exchange，提问作者Alessandro Aguilar