Word Break Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Break Check with Simple Dictionary

What is the output of this C code that checks if the string "leetcode" can be segmented into dictionary words?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
    int len = strlen(s);
    bool dp[len + 1];
    dp[0] = true;
    for (int i = 1; i <= len; i++) {
        dp[i] = false;
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                for (int k = 0; k < wordDictSize; k++) {
                    int wordLen = strlen(wordDict[k]);
                    if (wordLen == i - j && strncmp(s + j, wordDict[k], wordLen) == 0) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            if (dp[i]) break;
        }
    }
    return dp[len];
}

int main() {
    char *dict[] = {"leet", "code"};
    char s[] = "leetcode";
    if (wordBreak(s, dict, 2))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

A false

B true

C Compilation error

D Runtime error

💡 Hint

Think about whether the string "leetcode" can be split into words from the dictionary {"leet", "code"}.

The string "leetcode" can be segmented as "leet" + "code", both present in the dictionary, so the output is true.

❓ Predict Output

intermediate

Output when string cannot be segmented

What is the output of this C code that checks if the string "applepenapple" can be segmented into dictionary words {"apple", "pen", "pine"}?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
    int len = strlen(s);
    bool dp[len + 1];
    dp[0] = true;
    for (int i = 1; i <= len; i++) {
        dp[i] = false;
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                for (int k = 0; k < wordDictSize; k++) {
                    int wordLen = strlen(wordDict[k]);
                    if (wordLen == i - j && strncmp(s + j, wordDict[k], wordLen) == 0) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            if (dp[i]) break;
        }
    }
    return dp[len];
}

int main() {
    char *dict[] = {"apple", "pen", "pine"};
    char s[] = "applepenapple";
    if (wordBreak(s, dict, 3))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

A Runtime error

B false

C Compilation error

D true

💡 Hint

Check if the string can be split into words from the dictionary.

The string "applepenapple" can be segmented as "apple" + "pen" + "apple", all present in the dictionary, so the output is true.

❓ Predict Output

advanced

Output for string with no valid segmentation

What is the output of this C code that checks if the string "catsandog" can be segmented into dictionary words {"cats", "dog", "sand", "and", "cat"}?

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
    int len = strlen(s);
    bool dp[len + 1];
    dp[0] = true;
    for (int i = 1; i <= len; i++) {
        dp[i] = false;
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                for (int k = 0; k < wordDictSize; k++) {
                    int wordLen = strlen(wordDict[k]);
                    if (wordLen == i - j && strncmp(s + j, wordDict[k], wordLen) == 0) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            if (dp[i]) break;
        }
    }
    return dp[len];
}

int main() {
    char *dict[] = {"cats", "dog", "sand", "and", "cat"};
    char s[] = "catsandog";
    if (wordBreak(s, dict, 5))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

A Compilation error

B true

C false

D Runtime error

💡 Hint

Try to segment the string using the dictionary words.

The string "catsandog" cannot be segmented fully into the dictionary words because "og" is not in the dictionary, so output is false.

🧠 Conceptual

advanced

Understanding the DP Array in Word Break

In the Word Break problem, what does the boolean array dp represent during the algorithm execution?

A dp[i] is true if the substring s[0..i-1] can be segmented into dictionary words

B dp[i] is true if the substring s[i..end] can be segmented into dictionary words

C dp[i] stores the length of the longest dictionary word ending at index i

D dp[i] counts the number of dictionary words found up to index i

💡 Hint

Think about what the dp array tracks as the algorithm progresses from start to end.

dp[i] is true if the substring from the start of the string up to index i-1 can be segmented into dictionary words.

🚀 Application

expert

Number of Ways to Segment String Using Word Break

Given the string "catsanddog" and dictionary {"cat", "cats", "and", "sand", "dog"}, how many different ways can the string be segmented into dictionary words?

A 2

B 3

C 1

D 0

💡 Hint

Try to find all possible segmentations of the string using the dictionary words.

The string "catsanddog" can be segmented as "cats and dog" and "cat sand dog", so there are 2 ways.

Practice

1. What does the Word Break Problem ask you to determine about a given string s and a dictionary of words wordDict?

easy

A. If s contains any substring from wordDict

B. If s can be segmented into a space-separated sequence of one or more dictionary words

C. If s is exactly equal to any word in wordDict

D. If s is a palindrome

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if the entire string s can be split into parts where each part is a word in the dictionary.

2. Step 2: Compare options with the problem

   If s can be segmented into a space-separated sequence of one or more dictionary words correctly describes this segmentation into dictionary words. Other options describe different checks.

3. Final Answer:

   If s can be segmented into a space-separated sequence of one or more dictionary words -> Option B

4. Quick Check:

   Word Break Problem = segmentation check [OK]

Hint: Remember: Word Break means full segmentation into dictionary words [OK]

Common Mistakes:

• Thinking it checks for substring presence only
• Confusing exact match with segmentation
• Assuming palindrome check

2. Which of the following C code snippets correctly declares a function prototype for solving the Word Break Problem?

easy

A. int wordBreak(char s[], char *wordDict[], int wordDictSize);

B. void wordBreak(char s[], char wordDict[], int size);

C. int wordBreak(char *s, char *wordDict, int wordDictSize);

D. int wordBreak(char **s, char **wordDict, int wordDictSize);

Solution

1. Step 1: Understand parameter types for the Word Break function

   The string s is a character array, so char s[] or char *s works. The dictionary is an array of strings, so char *wordDict[] is correct. The size is an integer.

2. Step 2: Check each option

   int wordBreak(char s[], char *wordDict[], int wordDictSize); matches the correct signature: int wordBreak(char s[], char *wordDict[], int wordDictSize); int wordBreak(char *s, char *wordDict, int wordDictSize); uses char *wordDict which is incorrect for array of strings. void wordBreak(char s[], char wordDict[], int size); uses char wordDict[] which is incorrect for array of strings. int wordBreak(char **s, char **wordDict, int wordDictSize); uses char **s which is incorrect for a single string.

3. Final Answer:

   int wordBreak(char s[], char *wordDict[], int wordDictSize); -> Option A

4. Quick Check:

   Function prototype with string and array of strings = int wordBreak(char s[], char *wordDict[], int wordDictSize); [OK]

Hint: Dictionary is array of strings: use char *wordDict[] [OK]

Common Mistakes:

• Using char wordDict[] instead of array of strings
• Using char **s for input string
• Wrong return type or missing parameters

3. What will be the output of the following C code snippet for the Word Break Problem?

char *dict[] = {"leet", "code"};
int result = wordBreak("leetcode", dict, 2);
printf("%d", result);

Assuming wordBreak returns 1 if segmentation is possible, else 0.

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze the input string and dictionary

   The string is "leetcode" and dictionary contains "leet" and "code".

2. Step 2: Check if string can be segmented

   "leetcode" can be split as "leet" + "code", both in dictionary, so segmentation is possible.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   "leetcode" segmented as "leet" + "code" = 1 [OK]

Hint: Check if string splits fully into dictionary words [OK]

Common Mistakes:

• Assuming partial match is enough
• Confusing return values
• Ignoring dictionary contents

4. Identify the error in the following C code snippet for the Word Break Problem:

int wordBreak(char *s, char **wordDict, int wordDictSize) {
    int len = strlen(s);
    int dp[len+1];
    dp[0] = 1;
    for (int i = 1; i <= len; i++) {
        dp[i] = 0;
        for (int j = 0; j < i; j++) {
            if (dp[j] && strncmp(s+j, wordDict[i], i-j) == 0) {
                dp[i] = 1;
                break;
            }
        }
    }
    return dp[len];
}

medium

A. Missing return statement

B. dp array not initialized properly

C. Using wordDict[i] instead of wordDict[j] in strncmp

D. Loop indices are out of range

Solution

1. Step 1: Understand the nested loop and string comparison

   The inner loop checks substrings from index j to i. It should compare with wordDict[j], not wordDict[i].

2. Step 2: Identify the incorrect array index usage

   Using wordDict[i] is wrong because i goes up to length of s, which may exceed wordDictSize and is unrelated to dictionary indexing.

3. Final Answer:

   Using wordDict[i] instead of wordDict[j] in strncmp -> Option C

4. Quick Check:

   Index in dictionary should match substring start index [OK]

Hint: Check indices used for dictionary access in loops [OK]

Common Mistakes:

• Mixing loop variables for dictionary access
• Not initializing dp array correctly
• Ignoring return statement

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which approach correctly solves the Word Break Problem using dynamic programming in C?

hard

A. Use recursion without memoization to check all substring splits

B. Use a stack to store all dictionary words and pop when matched

C. Sort the dictionary and check if s starts with any word

D. Use a boolean dp array where dp[i] is true if s[0..i-1] can be segmented, then check all substrings ending at i

Solution

1. Step 1: Understand dynamic programming approach

   We create a boolean dp array where dp[i] is true if substring s[0..i-1] can be segmented into dictionary words.

2. Step 2: Check all substrings ending at each position

   For each position i, check all j < i where dp[j] is true and substring s[j..i-1] is in dictionary. If yes, set dp[i] true.

3. Step 3: Return dp[length of s]

   If dp at the end is true, the string can be segmented.

4. Final Answer:

   Use a boolean dp array where dp[i] is true if s[0..i-1] can be segmented, then check all substrings ending at i -> Option D

5. Quick Check:

   DP boolean array with substring checks = Use a boolean dp array where dp[i] is true if s[0..i-1] can be segmented, then check all substrings ending at i [OK]

Hint: Use dp array to track segmentation up to each index [OK]

Common Mistakes:

• Using recursion without memo causing timeout
• Sorting dictionary does not help segmentation
• Stack approach is incorrect for this problem