Question

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

Answer 1

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

#define DICTLEN 8
#define MAXLEN 256

// Dictionary words
const char* dict[DICTLEN] = {
    "future", "depends", "the", "on",
    "your", "dreams", "start", "today"
};

// Check if a substring is in the dictionary
bool isInDict(const char* word) {
    for (int i = 0; i < DICTLEN; i++) {
        if (strcmp(dict[i], word) == 0)
            return true;
    }
    return false;
}

bool wordBreak(const char* s) {
    int slen = strlen(s);
    bool result[MAXLEN] = {false};
    result[0] = true;

    for (int i = 1; i <= slen; i++) {
        for (int j = 0; j < i; j++) {
            if (result[j]) {
                char sub[MAXLEN];
                strncpy(sub, s + j, i - j);
                sub[i - j] = '\0';

                if (isInDict(sub)) {
                    result[i] = true;
                    break;
                }
            }
        }
    }

    return result[slen];
}

int main() {
    const char* s = "futuredependsonyourdreams";

    if (wordBreak(s))
        printf("The string can be segmented\n");
    else
        printf("The string cannot be segmented\n");
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

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

#define MAXLEN 256
#define DICTLEN 11

// Check if a word is in the dictionary
bool isInDict(const char* word, const char* dict[], int dictSize) {
    for (int i = 0; i < dictSize; i++) {
        if (strcmp(dict[i], word) == 0)
            return true;
    }
    return false;
}

// Recursive word break function
void wordBreak(const char* str, int strsize, const char* result, const char* dict[], int dictSize) {
    for (int i = 1; i <= strsize; i++) {
        char subStr[MAXLEN];
        strncpy(subStr, str, i);
        subStr[i] = '\0';

        if (isInDict(subStr, dict, dictSize)) {
            char currentResult[MAXLEN];
            if (i == strsize) {
                snprintf(currentResult, sizeof(currentResult), "%s%s", result, subStr);
                printf("%s\n", currentResult);
                return;
            } else {
                snprintf(currentResult, sizeof(currentResult), "%s%s ", result, subStr);
                wordBreak(str + i, strsize - i, currentResult, dict, dictSize);
            }
        }
    }
}

int main() {
    const char* dict[] = {
        "butterfly", "basketball", "bagpiper", "and", "play",
        "with", "butter", "fly", "basket", "ball", "bags"
    };
    const char* str = "butterflyplaybasketballwithbags";
    char result[MAXLEN] = "";

    wordBreak(str, strlen(str), result, dict, DICTLEN);

    return 0;
}



/*
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