php 中字符串的排列
我在查找长度大于 7 的字符串的字符串排列时遇到代码问题。例如“abcdefgh”。我必须找到长度不超过 12 的单词的排列。请检查我的代码并建议是否可以进行任何优化。
function permute($str)
{
if (strlen($str) < 2)
{
return array($str);
}
$permutations = array();
$tail = substr($str, 1);
foreach (permute($tail) as $permutation)
{
$length = strlen($permutation);
for ($i = 0; $i <= $length; $i++)
{
$permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
}
}
/* Return the result */
return $permutations;
}
$arr = permute('abcdefghijkl');
I have problem with my code while finding permutation of string for string with length greater than 7. For eg 'abcdefgh'. I have to find the permutation of word up to 12 length. Please review my code and suggest if any optimization can be done.
function permute($str)
{
if (strlen($str) < 2)
{
return array($str);
}
$permutations = array();
$tail = substr($str, 1);
foreach (permute($tail) as $permutation)
{
$length = strlen($permutation);
for ($i = 0; $i <= $length; $i++)
{
$permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
}
}
/* Return the result */
return $permutations;
}
$arr = permute('abcdefghijkl');
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
看来解决方案的核心应该在于不检查所有内容。例如，如果你给我单词“earthquakes”，那么应该立即显而易见的是，字典中没有任何以“qk”开头的单词，因此检查
qk _ _ _ _ _ _ 形式的所有排列_ _是不必要的。这种类型的检查将为您节省大量的比较和查找操作。仅此“qk”示例就可以排除 362,880 (9!) 个排列，否则您需要检查这些排列。因此，我不会计算所有排列，然后从字典中提取它是否与其中一个排列匹配，而是首先确保您生成的每个排列实际上都是一个可能的单词。
It seems like the core of the solution should lie in not checking everything. For example, if you give me the word "earthquakes", it should be immediately evident that there are no dictionary words for anything beginning with "qk", thus checking all permutations of the form
q k _ _ _ _ _ _ _ _ _is unnecessary. This type of check will save you a lot of comparison and lookup operations. This "qk" example alone would rule out 362,880 (9!) permutations that you would have needed to check otherwise.So instead of calculating ALL the permutations, then pulling from the dictionary if it matches one of the permutations, I would make sure that each permutation you're generating is actually a possible word first.