PHP获取与给定字符串匹配的给定数组的可能字符串组合

Question

我有一个包含一堆字符串的数组，我想找到所有可能的组合，无论它如何排序与给定的字符串/单词匹配。$dictionary = ['flow', 'stack', 'stackover', 'over', 'code'];input: stackoverflowoutput:#1 -> ['stack', 'over', 'flow']#2 -> ['stackover', 'flow']我尝试过的是，我需要排除不包含在输入字符串中的数组元素，然后尝试将每个合并的元素与它匹配，但我不确定并被卡住了。谁能帮我想办法解决这个问题？提前谢谢你，这是我到目前为止的代码<?php$dict = ['flow', 'stack', 'stackover', 'over', 'code'];$word = 'stackoverflow';$dictHas = [];foreach ($dict as $w) {    if (strpos($word, $w) !== false) {      $dictHas[] = $w;    }}$result = [];foreach ($dictHas as $el) {    foreach ($dictHas as $wo) {        $merge = $el . $wo;        if ($merge == $word) {        } elseif ((strpos($word, $merge) !== false) {        }    }}print_r($result);

Answer 1

对于这样的问题，您想使用回溯

function splitString($string, $dict)

{

    $result = [];

    //if the string is already empty return empty array

    if (empty($string)) {

        return $result;

    }

    foreach ($dict as $idx => $term) {

        if (strpos($string, $term) === 0) {

            //if the term is at the start of string

            //get the rest of string

            $substr = substr($string, strlen($term));

            //if all of string has been processed return only current term

            if (empty($substr)) {

                return [[$term]];

            }

            //get the dictionary without used term

            $subDict = $dict;

            unset($subDict[$idx]);

            //get results of splitting the rest of string

            $sub = splitString($substr, $subDict);

            //merge them with current term

            if (!empty($sub)) {

                foreach ($sub as $subResult) {

                    $result[] = array_merge([$term], $subResult);

                }

            }

        }

    }

    return $result;

}

$input = "stackoverflow";

$dict = ['flow', 'stack', 'stackover', 'over', 'code'];

$output = splitString($input, $dict);