使用哈希进行字符串比较

Question

所以我刚从一次出色的面试中出来，碰巧在最后丢了球。 我接受的测试涉及解决一个简单的CS问题。

你有两次刺痛 $a = 'abcd'; $b = 'cdfg';

使用最有效的方法，我被要求比较这两个字符串并返回任何匹配的字符。 当时，最明显（也是效率最低）的解决方案如下。

'

$matches = array();
$length = strlen($a);
for($i = 0; $i < $length; $i++) {
    if(strpos($b, $a[$i]) !== false) {
        $matches[] = $a[$i];
    }
}
return $matches;

我被告知，正确和最有效的解决方案需要使用哈希值。
有人可以详细说明吗？

编辑：

此示例中的返回值应为"cd"。

有人告诉我，使用诸如"array_intersect"之类的PHP方法将被视为作弊。

Answer 1

您的解决方案是 O(strlen($a) * strlen($b)) ，因为strpos()可能必须搜索所有$b才能找到特定的字符。 通过"哈希"，我假设它们的意思是"将$a的字符存储在哈希表中"：

$a_hash = array();
$length = strlen($a);
for ($i = 0; $i < $length; $i++) {
    $a_hash[$a[$i]] = true;
}
$matches = array();
$length = strlen($b);
for ($i = 0; $i < $length; $i++) {
   if (array_key_exists($a_hash, $b[$i])) {
       $matches[] = $b[$i];
   }
}
return $matches;

假设哈希表操作（使用PHP臭名昭著的array()）是常量时间，现在O(strlen($a) + strlen($b))。