Question

How to check whether a string can be segmented into a sequence of words from a dictionary in PHP

Answer 1

function isInDict(string $word, array $dict): bool {
    foreach ($dict as $d) {
        if ($d === $word) {
            return true;
        }
    }
    return false;
}

function wordBreak(string $str, array $dict, string $result = ""): bool {
    $len = strlen($str);

    for ($i = 1; $i <= $len; $i++) {
        $prefix = substr($str, 0, $i);
        if (isInDict($prefix, $dict)) {
            if ($i == $len) {
                $result .= $prefix;
                return true;
            }
            if (wordBreak(substr($str, $i), $dict, $result . $prefix . " ")) {
                return true;
            }
        }
    }

    return false;
}

$dict = ["future", "depends", "the", "on", "your", "dreams", "start", "today"];
$str = "futuredependsonyourdreams";

if (wordBreak($str, $dict)) {
    echo "The string can be segmented\n";
} else {
    echo "The string cannot be segmented\n";
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

function isInDict($word, $dict) {
    foreach ($dict as $entry) {
        if ($entry === $word) {
            return true;
        }
    }
    return false;
}

function wordBreak($str, $strsize, $result, $dict) {
    for ($i = 1; $i <= $strsize; $i++) {
        $subStr = substr($str, 0, $i);

        if (isInDict($subStr, $dict)) {
            if ($i == $strsize) {
                echo $result . $subStr . PHP_EOL;
                return;
            }
            wordBreak(substr($str, $i), $strsize - $i, $result . $subStr . " ", $dict);
        }
    }
}

$str = "butterflyplaybasketballwithbags";
$dict = ["butterfly", "basketball", "bagpiper", "and", "play",
         "with", "butter", "fly", "basket", "ball", "bags"];

wordBreak($str, strlen($str), "", $dict);



/*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*/

 

70+ SQL courses for beginners and professionals