Question

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

Answer 1

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

    for (let i: number = 1; i <= slen; i++) {
        for (let j: number = 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: Set<string> = new Set([
    "future", "depends", "the", "on",
    "your", "dreams", "start", "today"
]);

const s: string = "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: string, dict: string[]): boolean {
    return dict.includes(word);
}

function wordBreak(str: string, result: string, dict: string[]): void {
    const strsize: number = str.length;

    for (let i: number = 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: string = "butterflyplaybasketballwithbags";
const dict: string[] = [
    "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