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

Question

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

What should happen if the input string contains a substring that is not present in dictionary? What should happen if the input string contains single word from dictionary multiple times? — Michal Hynčica
– Michal Hynčica, Commented Sep 22, 2019 at 12:06
@MichalHynčica this case assumes that all of the substring present in dictionary and each of the dictionary's member is unique, which means no duplication — Aldi Unanto
– Aldi Unanto, Commented Sep 22, 2019 at 12:16

Michal Hynčica · Accepted Answer · 2019-09-22 13:05:32Z

3

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

edited Sep 22, 2019 at 13:05

answered Sep 22, 2019 at 12:48

Michal Hynčica

6,2711 gold badge16 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Aldi Unanto Over a year ago

I'm impressed this answer came so quick with this excellent and in simple way, great explanation and +1 for the reference you mentioned there. Thank you

Michal Hynčica Over a year ago

I've slightly edited the function because it was giving wrong result for "stackoveroverflow".

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related