PHP霍夫曼解码算法

Question

我最近申请了一份工作,并在几个问题上发了一个hackerrank考试.其中一个是霍夫曼解码算法.有可用的类似的问题在这里这也解释了格式化好了很多,然后我可以.

实际的任务是获取两个参数并返回已解码的字符串.

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

[
    "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获取第一个字符和正则表达式匹配以获得数字,但这仍然通过前两个并且未通过隐藏的五个.我尝试在黑客等级平台中使用白色空间作为输入,沙盒环境无法处理它,所以我恢复到上面的解决方案,因为它更优雅.

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

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

Answer 1

你的基本方法是正确的。由于霍夫曼代码是前缀代码，即没有代码是另一个代码的前缀，因此如果您的搜索找到匹配项，则该代码一定是该代码。代码的后半部分可以与任何正确的霍夫曼代码以及使用它编码的任何消息一起使用。

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

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

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