How to split text without spaces into a list of words using dictionary-based segmentation in C++

1 Answer

0 votes
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <optional>
#include <algorithm> 

/*
    Dictionary-based text segmentation:
    ----------------------------------
    Given a string with no spaces, we want to split it into valid words
    using a dictionary. For example: "thisisatest" → ["this", "is", "a", "test"].

    Approach:
    ---------
    We use dynamic programming (DP) to determine which prefixes of the string
    can be segmented. For each index i, dp[i] stores an optional index j such
    that substring(j, i) is a valid dictionary word and dp[j] is also valid.
    This allows us to reconstruct the segmentation by backtracking from the end.

    Why DP:
    -------
    - Efficient: O(n²) worst case, but fast in practice.
    - Clean: avoids recursion and repeated work.
    - Expressive: dp table clearly represents segmentation feasibility.

    Steps:
    ------
    1. Build a dictionary (unordered_set for O(1) lookup).
    2. Fill dp[]: dp[i] = index of previous split or nullopt if impossible.
    3. If dp[end] is valid, backtrack to recover the list of words.
*/

using Dictionary = std::unordered_set<std::string>;

// Attempts to segment `text` using `dict`.
// Returns a list of words if successful, otherwise an empty vector.
std::vector<std::string> segmentText(const std::string& text, const Dictionary& dict) {
    const int n = static_cast<int>(text.size());

    // dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid.
    // dp[0] = 0 means empty prefix is valid.
    std::vector<std::optional<int>> dp(n + 1, std::nullopt);
    dp[0] = 0;

    // Fill DP table
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            // Check whether dp[j] contains a valid split point;
            // if it does, it means the prefix text[0:j] can be segmented.
            if (dp[j].has_value()) {

                // Create a lightweight string_view representing the substring text[j:i].
                // This avoids unnecessary allocation; it simply views the existing buffer.
                const std::string_view candidate(text.data() + j, i - j);

                // Convert the string_view to a std::string so it can be checked in the dictionary.
                // Then verify whether this substring is a valid dictionary word.
                if (dict.count(std::string(candidate)) > 0) {

                    // Record that index j is the previous valid split before i.
                    // This means text[j:i] is a valid word and dp[j] was valid.
                    dp[i] = j;

                    // Stop searching for other j values because we already found
                    // a valid segmentation ending at i.
                    break;
                }
            }
        }
    }

    // If dp[n] is not set, segmentation is impossible
    if (!dp[n].has_value()) {
        return {};
    }

    // Backtrack to recover words
    std::vector<std::string> result;
    for (int i = n; i > 0; i = dp[i].value()) {
        int j = dp[i].value();
        result.emplace_back(text.substr(j, i - j));
    }

    // Words were collected backwards, reverse them
    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    // Example dictionary
    Dictionary dict = {
        "this", "is", "a", "test", "hello", "world", "foo", "bar"
    };

    // Example input
    std::string input = "thisisatestfoo";

    // Segment the text
    auto words = segmentText(input, dict);

    // Print results
    if (words.empty()) {
        std::cout << "No valid segmentation found.\n";
    } else {
        std::cout << "Segmentation result:\n";
        for (const auto& w : words) {
            std::cout << w << "\n";
        }
    }
}


/*
run:

Segmentation result:
this
is
a
test
foo

*/

 



answered Sep 6 by avibootz

Related questions

...