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.