Задачка по PHP , на обработку/классификацию строк.

Необходимо написать функцию, которая принимает на вход массив со списком слов

и возвращает сгруппированные слова.

К одной группе относятся слова, которые могут быть получены одно из другого

с помощью произвольной перестановки букв. (см. примеры ниже)

Пример работы функции:

<?php

/*
Необходимо написать функцию, которая принимает на вход массив со списком слов 
и возвращает сгруппированные слова.
К одной группе относятся слова, которые могут быть получены одно из другого 
с помощью произвольной перестановки букв.
 
Например:
    makeGroups( array('rfv', 'vfr', 'abc', 'bac', 'dbatre', 'qwer', 'cba', 'terbda') )
 
Вернет:
    array(
        array('rfv', 'vfr'),
        array('abc', 'bac', 'cba'),
        array('dbatre', 'terbda'),
        array('qwer'),
    )
 
Здесь rfv получается из vfr с помощью перестановки v и r, а из слов abc, 
bac и cba формируется общая группа, 
потому что любое из этих слов превращается в соседнее путём одной 
или нескольких перестановок букв.
 
Протестируйте свой код.
*/

function makeGroups(array $words): array {
	return [
		['rfv', 'vfr'],
		['abc', 'bac', 'cba'],
		['dbatre', 'terbda'],
		['qwer'],
	];
};
$r = makeGroups( array('rfv', 'vfr', 'abc', 'bac', 'dbatre', 'qwer', 'cba', 'terbda') );
print_r($r);
exit;

Мое решение:

<?php

/**
 * Calc string hah
 * @param string $word
 * @return string
 */
function calcHash(string $word): string
{
	$hash = '';

	$cnt = [];
	for($i = 0; $i < mb_strlen($word); $i++) {
		$chr = mb_substr($word, $i, 1);
		if(isset($cnt[$chr])) {
			$cnt[$chr]++;
		} else {
			$cnt[$chr] = 1;
		}
	}

	ksort($cnt);

	$hash = md5(json_encode($cnt));

	return $hash;
}

/**
 * Make words groups
 * @param array $words
 * @return array
 */
function makeGroups(array $words): array
{
	$ret = [];

	foreach($words as $word) {
		$hash = calcHash($word);
		//echo "Hash for $word: $hashn";
		$ret[$hash][] = $word;
	}

	return array_values($ret);
};

$r = makeGroups( array('rfv', 'vfr', 'abc', 'bac', 'dbatre', 'qwer', 'cba', 'terbda') );
print_r($r);
exit;

~ Я решил за ~50 мин, вкл. обсуждение

Tags

Нет комментариев

Добавить комментарий

Ваш адрес email не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.