Word Break Problem in DSA C - 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 valid words from a dictionary. This is like trying to read a message where spaces are missing and figuring out if it makes sense.

🎯 Goal: You will build a program that checks if a given string can be segmented into a sequence of dictionary words. This helps understand how to use arrays and loops to solve problems step-by-step.

📋 What You'll Learn

Create a string variable called input with the exact value "applepenapple".

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

Create an integer variable called dictSize and set it to 2.

Create an integer array called dp with size strlen(input) + 1.

Write a loop to fill dp with zeros and set dp[0] to 1.

Use nested loops to check all substrings of input and update dp to mark valid breaks.

Print "true" if the whole string can be segmented, otherwise print "false".

💡 Why This Matters

🌍 Real World

This problem helps in text processing tasks like spell checking, auto-correct, and natural language processing where words need to be identified in a continuous text.

💼 Career

Understanding this problem shows your ability to use arrays, loops, and string functions in C, which are essential skills for software development and technical interviews.

1

Create the input string and dictionary

Create a string variable called input with the value "applepenapple". Create an array of strings called dictionary with the words "apple" and "pen". Create an integer variable called dictSize and set it to 2.

DSA C

# Create the input string and dictionary array
# Your code here

Hint

Use char input[] = "applepenapple"; to create the input string. Use char *dictionary[] = {"apple", "pen"}; for the dictionary words. Set dictSize to 2.

2

Create the dp array and initialize it

Create an integer array called dp with size strlen(input) + 1. Write a loop to fill dp with zeros and set dp[0] to 1.

DSA C

#include 
#include 

char input[] = "applepenapple";
char *dictionary[] = {"apple", "pen"};
int dictSize = 2;

// Create dp array and initialize
# Your code here

Hint

Use int dp[100]; to create the array. Use a for loop from 0 to strlen(input) to set all dp[i] to 0. Then set dp[0] = 1;.

3

Implement the word break logic

Use nested for loops with variables i and j to check all substrings of input. For each substring, check if dp[j] is 1 and if the substring input[j..i-1] matches any word in dictionary. If yes, set dp[i] to 1.

DSA C

#include 
#include 

char input[] = "applepenapple";
char *dictionary[] = {"apple", "pen"};
int dictSize = 2;

int dp[100];

int main() {
    int length = strlen(input);
    for (int i = 0; i <= length; i++) {
        dp[i] = 0;
    }
    dp[0] = 1;

    // Use nested loops to check substrings and update dp
    // Your code here

    return 0;
}

Hint

Use two loops: outer loop i from 1 to length, inner loop j from 0 to i-1. Check if dp[j] is 1 and substring matches a dictionary word using strncmp. If yes, set dp[i] = 1.

4

Print the result

Write a printf statement to print "true" if dp[length] is 1, otherwise print "false".

DSA C

#include 
#include 

char input[] = "applepenapple";
char *dictionary[] = {"apple", "pen"};
int dictSize = 2;

int dp[100];

int main() {
    int length = strlen(input);
    for (int i = 0; i <= length; i++) {
        dp[i] = 0;
    }
    dp[0] = 1;

    for (int i = 1; i <= length; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                int wordLen = i - j;
                for (int k = 0; k < dictSize; k++) {
                    if (strlen(dictionary[k]) == wordLen && strncmp(&input[j], dictionary[k], wordLen) == 0) {
                        dp[i] = 1;
                        break;
                    }
                }
            }
            if (dp[i]) {
                break;
            }
        }
    }

    // Print "true" if dp[length] is 1 else "false"
    # Your code here

    return 0;
}

Hint

Use if (dp[length]) to check if the string can be segmented. Print "true" if yes, otherwise print "false".