如何检查是否可以从字母列表中创建单词？

Question

我有一个字符串 $raw="aabbcdfghmnejaachto" 和一个数组 $word_array=array('cat','rat','goat','total','egg')。

我的程序需要检查是否可以用字符串中的字母组成数组中的单词。还有一个额外条件；如果单词包含一个字母出现多次，则该字母在字符串中出现的次数必须至少相同。

例如egg。有两个 g。如果字符串 $raw 不包含两个 g，那么就不可能组成这个词。

这是我的预期结果：

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

我尝试了以下方法，但没有输出预期的结果：

$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);

编辑： 最初发布的代码缺少字符串 $raw 中的字母 e 因此 egg 示例将实际上 return No。我已经更新了问题和所有答案以反映这一点。 - robinCTS

Answer 1

你的问题是你没有计算每个字符在 $raw 数组中出现的次数，你只是检查每个单词中的每个字符以查看该字符是否存在于 $raw.除非你进行某种形式的计数，或者为每个单词复制 $raw 并在使用时删除字母，否则你将无法做到这一点。

Answer 2

你这里的错误很明显，你决定一个单词是否接受一个值是通过对字符的单独测试，而它应该基于单词的所有字母，你不需要精确数组的键和值，如果你只需要它的值如

foreach($word_array as $value)

然后我发现函数的使用in_array()，让代码更清晰

$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);

Answer 3

试试这个

$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)]);
        }
    }
}

这将不允许再次使用字符，如果它被使用一次像"total"。

Answer 4

我计算了字符串中字符的出现次数并比较了出现的次数！您会发现这个答案有效！！！

$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);

Answer 5

您必须遍历 $words 数组中的每个 word/element，然后再次遍历每个单词的每个字符。
在外循环的每次迭代中，将默认结果值设置为Yes。
然后你必须迭代当前单词的每个唯一字符。 (array_count_values())
检查当前字符在单词中出现的次数是否大于当前字符在字符串中出现的次数

*作为性能优化的问题，array_count_values() 用于内部循环以避免在 $word 中重复字母的任何不必要的迭代。 $count 变量避免了在 if 语句中进行两次 substr_count() 调用。

代码：(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);

这是输出：

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

非常感谢 到 mickmackusa 劫持显着增强了这个答案。

Answer 6

让我们试着让它 w/o 循环，但要有闭包：

$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';
    }
);

我们正在构建一个符号映射，在带有 count_chars($raw, 1) 的原始字符串中使用，因此它看起来像这样。

$map:

[
    97 => 4, // "97" is a code for "a"; and "4" - occurrence number.
    98 => 2,
    ...
]

array_walk 遍历单词并将每个单词添加到最终的 $result 中，并带有来自比较的 Yes 或 No 值有一张地图，那是为一个词而建的。
array_udiff_assoc 比较两个映射，丢弃那些具有相同键和值的原始映射更大的元素（与单词映射相比）。还有 array_udiff_assoc() returns 一个数组，其中包含 array1 中不存在于任何其他参数 中的所有值，因此最后一步是否定运算在 array_udiff_assoc.

Demo

Answer 7

我们可以检查每个单词的每个字母是否在给定的字母范围内，并在进行时将找到的字母取出。

如果找不到字母，下面的函数会短路。

<?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);

输出：

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)

如何检查是否可以从字母列表中创建单词？

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

php

arrays

string

loops

words