Question

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

Answer 1

function wordBreak(s, dict) {
    const slen = s.length;
    const result = new Array(slen + 1).fill(false);
    result[0] = true; // empty string is always segmentable

    for (let i = 1; i <= slen; i++) {
        for (let j = 0; j < i; j++) {
            const sub = s.substring(j, i);
            if (result[j] && dict.has(sub)) {
                result[i] = true;
                break;
            }
        }
    }

    return result[slen];
}

const dict = new Set([
    "future", "depends", "the", "on",
    "your", "dreams", "start", "today"
]);

const s = "futuredependsonyourdreams";

if (wordBreak(s, dict)) {
    console.log("The string can be segmented");
} else {
    console.log("The string cannot be segmented");
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

function isInDict(word, dict) {
    return dict.includes(word);
}

function wordBreak(str, result, dict) {
    const strsize = str.length;

    for (let i = 1; i <= strsize; i++) {
        const subStr = str.substring(0, i);

        if (isInDict(subStr, dict)) {
            if (i === strsize) {
                console.log(result + subStr);
                return;
            }

            wordBreak(str.substring(i), result + subStr + " ", dict);
        }
    }
}

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

wordBreak(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