CODEWITHSUNDEEP
phparrays
Aldi Unanto
Aldi Unanto

Reputation: 3682

PHP get possible string combination of given array which match with given string

I have an array which contains bunch of strings, and I would like to find all of the possible combinations no matter how it's being sorted that match with given string/word.

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

input: stackoverflow
output:
#1 -> ['stack', 'over', 'flow']
#2 -> ['stackover', 'flow']

What I've tried is, I need to exclude the array's element which doesn't contain in an input string, then tried to match every single merged element with it but I'm not sure and get stuck with this. Can anyone help me to figure the way out of this? thank you in advance, here are my code so far

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

Upvotes: 3

Views: 141

Answers (1)

Michal Hynčica
Michal Hynčica

Reputation: 6144

For problems like this you want to use 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);

Upvotes: 3

Related Questions