PHP哈夫曼解码算法

Question

我最近申请了一份工作，收到了一个 hackerrank 考试，有几个问题。其中一个是霍夫曼解码算法。有类似问题可用here这比我能更好地解释格式。

实际任务是接受两个参数并返回解码后的字符串。

第一个参数是代码，它是一个字符串数组，如:

[
    "a      00",
    "b      101",
    "c      0111",
    "[newline]      1001"
]

这就像:单个字符，两个制表符，霍夫曼代码。

由于黑客排名的设置方式，换行符被指定为这种格式。

第二个参数是要使用代码解码的字符串。例如:

101000111 = bac

这是我的解决方案:

function decode($codes, $encoded) {
    $returnString = '';
    $codeArray = array();

    foreach($codes as $code) {
        sscanf($code, "%s\t\t%s", $letter, $code);
        if ($letter == "[newline]")
            $letter = "\n";
        $codeArray[$code] = $letter;
    }
    print_r($codeArray);

    $numbers = str_split($encoded);
    $searchCode = '';
    foreach ($numbers as $number) {
        $searchCode .= $number;
        if (isset($codeArray[$searchCode])) {
            $returnString .= $codeArray[$searchCode];
            $searchCode = '';
        }
    }

    return $returnString;
}

它通过了两个初始测试，但还有另外五个隐藏测试没有通过并且没有给出任何反馈。

我意识到如果字符是空格，这个解决方案将不会通过，所以我尝试了一个不太理想的解决方案，该解决方案使用 substr 获取第一个字符并使用正则表达式匹配获取数字，但这仍然通过了前两个并且失败了隐藏五。我尝试在 hacker rank 平台中使用空格作为输入的函数，但沙盒环境无论如何都无法处理它，所以我恢复到上面的解决方案，因为它更优雅。

我用特殊字符、其他语言的字符、各种大小的代码尝试了代码，它总是返回所需的解决方案。

我很沮丧，因为我发现这是一个优雅的解决方案，所以找不到导致失败的案例。我希望得到一些关于为什么在没有空白的情况下这会失败的反馈，以及任何关于性能提升的反馈。

Answer 1

您的基本方法是合理的。由于霍夫曼代码是前缀代码，即没有代码是另一个代码的前缀，那么如果您的搜索找到匹配项，那么它一定是代码。您的代码的后半部分适用于任何适当的霍夫曼代码以及使用它编码的任何消息。

一些评论。首先，您提供的示例不是霍夫曼代码，因为前缀 010、0110、1000 和 11 不存在。霍夫曼码是完备的，而这个前缀码不是。

这会带来第二个问题，即您没有检测到此错误。您应该在循环结束后检查 $searchCode 是否为空。如果不是，则代码不完整，或者代码在中间结束。无论哪种方式，消息相对于提供的前缀代码都是损坏的。问题是否具体说明了如何处理错误？

我认为此代码唯一真正的问题是您没有对代码描述进行足够全面的解码。问题是说总是有两个选项卡，还是您得出结论？也许它只是任意数量的空间和制表符。哪里有你需要转换的其他字符编码，比如 [newline]？我假设您实际上确实需要转换它们，如果其中一个有效的示例包含一个。做到了？否则，也许您不应该转换。