How to check if words can be created from list of letters?


Keywords:php 


Question: 

I have a string $raw="aabbcdfghmnejaachto" and an array $word_array=array('cat','rat','goat','total','egg').

My program needs to check whether it is possible to make the words in the array with letters from the string. There is one extra condition; if the word contains a letter occurring more than once, that letter must occur at least the same number of times in the string.

E.g. egg. There are two g's. If the string $raw doesn't contain two g's, then it's not possible to make this word.

This is my expected result:

Array([cat]=>'Yes',[rat]=>'No',[goat]=>'Yes',[total]=>'No',[egg]=>'No')

I tried the following, but it doesn't output the expected result:

$res=array();
$raw="aabbcdfghmnejaachto";
$word_array=array('cat','rat','goat','total','egg');
$raw_array= str_split($raw);
foreach($word_array as $word=>$value)
{
    $word_value= str_split($value);
    foreach($word_value as $w=>$w_value)
    {
        foreach($raw_array as $raw=>$raw_value)
        {
            if(strcmp($w_value,$raw_value)==0)
            {
                $res[$value]='Yes';
            }
            else
            {
                $res[$value]='No';
            }
        }
    }
}
print_r($res);

EDIT: The code, as originally posted, was missing the letter e from the string $raw so the egg example would actually return No. I have updated the Question and all the Answers to reflect this. - robinCTS


7 Answers: 

  • You must loop through each word/element in the $words array, then loop again through each character of each word.
  • Upon each iteration of the outer loop, set the default result value to Yes.
  • Then you must iterate each unique character of the current word. (array_count_values())
  • Check if the number of occurrences of the current character in the word is greater than the number of occurrences of the current character in the string of letters.

*As a matter of performance optimization, array_count_values() is used on the inner loop to avoid any unnecessary iterations of duplicate letters in $word. The $count variable saves having to make two substr_count() calls in the if statement.

Code: (Demo)

$string = "aabbcdfghmnejaachto";
$words = array('cat','rat','goat','total','egg');
foreach ($words as $word) {  // iterate each word
    $result[$word]='Yes';  // set default result value
    foreach (array_count_values(str_split($word)) as $char=>$count) {  // iterate each unique letter in word
        if ($count > substr_count($string, $char)) {  // compare current char's count vs same char's count in $string
            $result[$word]='No';  // if more of the character in word than available in $string, set No
            break;  // make early exit from inner loop, to avoid unnecessary iterations
        }
    }    
}
var_export($result);

This is the output :

array (
  'cat' => 'Yes',
  'rat' => 'No',
  'goat' => 'Yes',
  'total' => 'No',
  'egg' => 'No',
)

BIG THANKYOU to mickmackusa for hijacking significantly enhancing this answer.



Your problem is you are not counting the number of times each character occurs in the $raw array, you are just checking each character in each of the words to see if that character exists in $raw. Unless you put in some form of counting, or else make a copy of $raw for each word and remove letters as they are used, you are not going to be able to do this.



I have counted occurrences of characters in string and compare that number of occurrence! You can find this answer working!!!

$res=array();
$raw="aabbcdfghmnejaachto"; //tgrel -- to make all yes
$res=array();
$word_array=array('cat','rat','goat','total','egg');
$raw_array= str_split($raw);
$count_raw = array_count_values($raw_array);

foreach($word_array as $value)
{
    $word_value= str_split($value);
    $newArray = array_count_values($word_value);
    $res[$value]='yes';
    foreach($newArray as $char=>$number){
        if(!isset($count_raw[$char]) || $count_raw[$char]<$number){
            $res[$value]='No';
            break;
        }
    }
}
print_r($res);


Your error here is obvious, that you decided whether a value a word is accepted or not on individual tests of characters, while it should be based on the all the letter of the word , you don't need to precise both the key and value of an array if you need only its value as in

foreach($word_array as $value)

then I've found that the use of the function in_array(), make the code much clearer

$res=array();
$raw="aabbcdfghmnejaachto";
$res=array();
$word_array=array('cat','rat','goat','total','egg');
$raw_array= str_split($raw);

foreach($word_array as $value)
{
    $word_value= str_split($value);
    $res[$value]='yes';
    foreach($word_value as $w_value)
    {
        if (!in_array($w_value,$raw_array))
            $res[$value]='No';

    }
}
print_r($res);


Lets try to make it w/o loops, but with closures:

$raw = "aabbcdfghmnejaachto";
$word_array = ['cat', 'rat', 'goat', 'total', 'egg'];

$result = [];
$map = count_chars($raw, 1);
array_walk(
    $word_array,
    function ($word) use ($map, &$result) {
        $result[$word] = !array_udiff_assoc(
            count_chars($word, 1), $map, function ($i, $j) { return $i > $j; }
        ) ? 'Yes' : 'No';
    }
);
  1. We are building a map of symbols, used in original string with count_chars($raw, 1), so it will look like this.

$map:

[
    97 => 4, // "97" is a code for "a"; and "4" - occurrence number.
    98 => 2,
    ...
]
  1. array_walk goes through words and adds each of them in a final $result with a Yes or No values that come from a comparison with a map, that was built for a word.

  2. array_udiff_assoc compares two maps, throwing away those elements that have the same key and values bigger for an original map (comparing with a map for a word). Also array_udiff_assoc() returns an array containing all the values from array1 that are not present in any of the other arguments, so the final step is a negation operation preceding array_udiff_assoc.

Demo



Try this

$res=array();
$word_array=array('cat','rat','goat','total','egg');
$raw="aabbcrdfghmnejaachtol";
foreach($word_array as $word=>$value)
{
    $raw_array= str_split($raw);
    $res[$value]='Yes';
    $word_value= str_split($value);
    foreach($word_value as $w=>$w_value)
    {
        if(!in_array($w_value,$raw_array))
        {
             $res[$value]='No';
        }
        else
        {
            unset($raw_array[array_search($w_value, $raw_array)]);
        }
    }
}

This will not allow character again, if it is used once Like "total".



We can check to see if each letter from each word is within the letters given, and pluck found letters out as we go.

The function below short circuits if a letter is not found.

<?php
function can_form_word_from_letters($word, $letters) {
    $letters      = str_split($letters);
    $word_letters = str_split($word);
    foreach($word_letters as $letter) {
        $key = array_search($letter, $letters);
        if($key === false) return;
        unset($letters[$key]); // Letter found, now remove it from letters.
    }
    return true;
}

$letters = "aabbcdfghmnejaachto";
$words   = array('cat','rat','goat','total','egg');

foreach($words as $word) {
    $result[$word] = can_form_word_from_letters($word, $letters) ? 'Yes' : 'No';
}

var_dump($result);

Output:

array (size=5)
  'cat' => string 'Yes' (length=3)
  'rat' => string 'No' (length=2)
  'goat' => string 'Yes' (length=3)
  'total' => string 'No' (length=2)
  'egg' => string 'No' (length=2)