greenba Posted October 22, 2009 Share Posted October 22, 2009 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 Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/ Share on other sites More sharing options...
Garethp Posted October 22, 2009 Share Posted October 22, 2009 preg_match_all("~([cktrut]*)~", $input, $Matches); print_r($Matches); Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/#findComment-942068 Share on other sites More sharing options...
cags Posted October 22, 2009 Share Posted October 22, 2009 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? Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/#findComment-942079 Share on other sites More sharing options...
dreamlove Posted October 22, 2009 Share Posted October 22, 2009 first check strlen(each element in array) == count of chars. then check if each char of the element is in array('c','k',..... Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/#findComment-942080 Share on other sites More sharing options...
greenba Posted October 22, 2009 Author Share Posted October 22, 2009 Thank you cags, that is what I meant a php anagram solver. Any further ideas? Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/#findComment-942089 Share on other sites More sharing options...
Daniel0 Posted October 22, 2009 Share Posted October 22, 2009 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. Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/#findComment-942111 Share on other sites More sharing options...
Daniel0 Posted October 22, 2009 Share Posted October 22, 2009 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. Link to comment https://forums.phpfreaks.com/topic/178615-find-in-a-string/#findComment-942120 Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.