所以我刚从一次出色的面试中出来，碰巧在最后丢了球。 我接受的测试涉及解决一个简单的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方法将被视为作弊。
您的解决方案是 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))。