Word Break Problem in DSA Typescript - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string of letters without spaces, and you want to check if it can be split into meaningful words from a given list. This is like trying to find spaces in a sentence that someone wrote without pressing the spacebar.

🎯 Goal: You will build a program that checks if a given string can be segmented into a sequence of dictionary words.

📋 What You'll Learn

Create a string variable with a specific sentence without spaces

Create an array of strings representing the dictionary words

Write a function that checks if the string can be segmented into dictionary words

Print the result as true or false

💡 Why This Matters

🌍 Real World

This problem is useful in text processing, like splitting words in languages without spaces or in spell checkers.

💼 Career

Understanding this problem helps in roles involving natural language processing, search engines, and software that processes human language.

1

Create the input string

Create a string variable called inputString and set it to "applepenapple".

DSA Typescript

# Your code here

Hint

Use const to create a string variable named inputString.

2

Create the dictionary array

Create an array of strings called dictionary with these exact words: "apple", "pen".

DSA Typescript

const inputString = "applepenapple";
# Your code here

Hint

Use const to create an array named dictionary with the words inside square brackets.

3

Write the word break function

Write a function called wordBreak that takes inputString and dictionary as parameters and returns true if inputString can be segmented into words from dictionary, otherwise false. Use a loop and recursion or dynamic programming inside the function.

DSA Typescript

const inputString = "applepenapple";
const dictionary = ["apple", "pen"];

# Your code here

Hint

Use a boolean array dp to keep track of valid breaks. Loop through the string and check substrings against the dictionary.

4

Print the result

Use console.log to print the result of calling wordBreak with inputString and dictionary.

DSA Typescript

const inputString = "applepenapple";
const dictionary = ["apple", "pen"];

function wordBreak(s: string, wordDict: string[]): boolean {
    const dp: boolean[] = new Array(s.length + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordDict.includes(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];
}

# Your code here

Hint

Call console.log(wordBreak(inputString, dictionary)) to see if the string can be segmented.