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