*/ private array $inputArray; public function __construct(string $input) { $this->input = $input; $this->inputLowerCase = strtolower($input); $this->inputArray = self::stringToArray($this->inputLowerCase); } public function measure(string $option, float $threshold): ?int { if ($this->input === $option) { return 0; } $optionLowerCase = strtolower($option); // Any case change counts as a single edit if ($this->inputLowerCase === $optionLowerCase) { return 1; } $a = self::stringToArray($optionLowerCase); $b = $this->inputArray; if (count($a) < count($b)) { $tmp = $a; $a = $b; $b = $tmp; } $aLength = count($a); $bLength = count($b); if ($aLength - $bLength > $threshold) { return null; } /** @var array> $rows */ $rows = []; for ($i = 0; $i <= $bLength; ++$i) { $rows[0][$i] = $i; } for ($i = 1; $i <= $aLength; ++$i) { $upRow = &$rows[($i - 1) % 3]; $currentRow = &$rows[$i % 3]; $smallestCell = ($currentRow[0] = $i); for ($j = 1; $j <= $bLength; ++$j) { $cost = $a[$i - 1] === $b[$j - 1] ? 0 : 1; $currentCell = min( $upRow[$j] + 1, // delete $currentRow[$j - 1] + 1, // insert $upRow[$j - 1] + $cost, // substitute ); if ($i > 1 && $j > 1 && $a[$i - 1] === $b[$j - 2] && $a[$i - 2] === $b[$j - 1]) { // transposition $doubleDiagonalCell = $rows[($i - 2) % 3][$j - 2]; $currentCell = min($currentCell, $doubleDiagonalCell + 1); } if ($currentCell < $smallestCell) { $smallestCell = $currentCell; } $currentRow[$j] = $currentCell; } // Early exit, since distance can't go smaller than smallest element of the previous row. if ($smallestCell > $threshold) { return null; } } $distance = $rows[$aLength % 3][$bLength]; return $distance <= $threshold ? $distance : null; } /** * Returns a list of char codes in the given string. * * @return array */ private static function stringToArray(string $str): array { $array = []; foreach (mb_str_split($str) as $char) { $array[] = mb_ord($char); } return $array; } }