해시를 사용한 문자열 비교

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))이라고 가정.