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

Question

我有一个包含一堆字符串的数组，我想找到所有可能的组合，无论它是如何排序的，与给定的字符串/单词匹配。

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

input: stackoverflow
output:
#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

对于这样的问题你想使用backtracking

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