Find in a string

[greenba]

Hello,

 

I am making an application that reads couple of chars, and then goes thru an array, and looks up for a string matching those characters..

 

example:

in my array I have; car, truck, house, red, color

 

and now I provide few characters as: c,k,r,u,t

 

so the script would check the array, and give back the string "truck".

 

Any ideas?

Adnan

[Garethp]

preg_match_all("~([cktrut]*)~", $input, $Matches);

 

print_r($Matches);

[cags]

preg_match_all("~([cktrut]*)~", $input, $Matches);

 

print_r($Matches);

 

How is that supposed to work? That will allow a string of any length that contains any of those characters, not to mention the fact you have t in there twice. The objective would seem to be to take an array of characters, attempt all possible orders and compare them against an array of words. In other words is an anagram solver, is that correct greenba?

[dreamlove]

first check strlen(each element in array) == count of chars.

then check if each char  of the element  is  in array('c','k',.....

 

 

[greenba]

Thank you cags, that is what I meant a php anagram solver.

Any further ideas?

[Daniel0]

You can generate all the permutations like this:

<?php
function generatePermutations(array $chars)
{
$numChars = count($chars);

if ($numChars == 1) {
	return $chars;
}

$permutations = array();

for ($i = 0; $i < $numChars; ++$i) {
	$orig = $chars;

	$first = $chars[$i];
	array_splice($chars, $i, 1); // why the hell can't it just return my new array?!
	foreach (generatePermutations($chars) as $str) {
		$permutations[] = $first . $str;
	}

	$chars = $orig;
}

return $permutations;
}

var_dump(generatePermutations(array('c', 'k', 'r', 'u', 't')));

 

Then you can check if the word is part of the permutations. You could also modify the algorithm to stop when the permutation has been found.

 

Note that this algorithm is Θ(n!) (we also say that it's running in factorial time), i.e. it quickly becomes slow if you have a lot of characters. For just 10 characters there will be 3628800 different permutations.

[Daniel0]

Okay, so this algorithm is much better:

 

<?php
function verifyAnagram(array $words, array $chars)
{
$numChars = count($chars);
sort($chars);

for ($i = 0, $num = count($words); $i < $num; ++$i) {
	if (strlen($words[$i]) === $numChars) {
		$c = str_split($words[$i]);
		sort($c);

		if ($c !== $chars) {
			unset($words[$i]);
		}
	}
	else {
		unset($words[$i]);
	}
}

sort($words); // to restore array keys

return $words;
}

var_dump(verifyAnagram(array('car', 'truck', 'house', 'red', 'color'), array('c', 'k', 'r', 'u', 't')));

 

It'll return all words that can be generated using the characters.