Word break problem: Difference between revisions
C++ - now a translation of Rust
m (→{{header|REXX}}: added/changed whitespace and comments.) |
(C++ - now a translation of Rust) |
||
Line 67:
=={{header|C++}}==
{{trans|Rust}}
<lang cpp>#include <algorithm>
#include <iostream>
#include <
#include <set>
#include <string>
#include <string_view>
#include <vector>
struct string_comparator {
using is_transparent = void;
bool operator()(const std::string& lhs, const std::string& rhs) const {
return lhs < rhs;
}
bool operator()(const std::string& lhs, const std::string_view& rhs) const {
return lhs < rhs;
}
bool operator()(const std::string_view& lhs, const std::string& rhs) const {
return lhs < rhs;
}
};
template <typename iterator, typename separator>
std::string join(iterator begin, iterator end, separator sep) {
std::string result;
result += *begin++;
for (; begin != end; ++begin)
result +=
}
return
}
const std::vector<std::optional<size_t>>& v) {
auto idx =
std::vector<std::string_view> sv;
while (v[idx].has_value()) {
}
std::reverse(sv.begin(), sv.end());
return join(sv.begin(), sv.end(), ' ');
}
const dictionary& dict) {
auto size = str.size() + 1;
std::vector<std::optional<size_t>> possible(size);
auto check_word = [&dict, &str](size_t i, size_t j)
-> std::optional<size_t> {
if (dict.find(str.substr(i, j - i)) != dict.end())
return i;
return std::nullopt;
};
for (size_t i = 1; i < size; ++i) {
if (!possible[i].has_value())
possible[i] = check_word(0, i);
if (possible[i].has_value()) {
for (size_t j = i + 1; j < size; ++j) {
if (!possible[j].has_value())
possible[j] = check_word(i, j);
}
if (possible[str.size()].has_value())
return create_string(str, possible);
}
}
return std::nullopt;
}
int main(int argc, char** argv) {
dictionary dict;
dict.insert("a");
dict.insert("bc");
dict.insert("abc");
dict.insert("cd");
auto result =
if (result.has_value())
return 0;
}
</lang>
{{out}}
Using the dictionary at http://wiki.puzzlers.org/pub/wordlists/unixdict.txt:
<pre>
a b cd
</pre>
| |||