Сравнение строк с использованием хэша
Так что я только что вышел из отличного интервью, в котором мне довелось бросить мяч к концу. Тест, который мне дали, включал решение простого вопроса 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».
Мне сказали, что использование методов PHP, таких как «array_intersect», будет считаться обманом.
Решение
Ваше решение 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)),
Другие решения
Других решений пока нет …