問題文が入手できないため、次のように仮定しています。
- フレーズの合計単語は、 内の合計文字数を使用する必要があります
[]が、各単語が 内の正確な文字数ではありません[]。
- フレーズは、
[]
- 単語を複数回使用できます (単語を 1 回だけ使用するように簡単に更新できます)
- 使用する単語は小文字で入力します。
- フレーズで使用する文字は大文字で入力します。
コード (C++11 を使用した GCC 4.9.0 でテスト済み):
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
bool can_use_word(std::vector<long>& chars_in_phrase, const std::string& word) {
unsigned int idx = 0;
bool valid = true;
// Verifing that the word could be used, that no char is used more that the
// phrase indicate
// Updating the char use count in place.
for (; idx < word.size(); idx++) {
if (chars_in_phrase[word[idx] - 'a'] == 0) {
valid = false;
break;
}
chars_in_phrase[word[idx] - 'a']--;
}
if (!valid) {
// If invalid revert the char use count as before.
for (unsigned int idx_revert = 0; idx_revert < idx; idx_revert++) {
chars_in_phrase[word[idx_revert] - 'a']++;
}
return false;
}
return true;
}
bool solve_phrase(std::vector<long>& chars_in_phrase,
std::vector<long>& phrase_word_length,
const std::vector<std::string>& words_to_use,
std::vector<std::string>& phrase,
unsigned int phrase_word_idx = 0) {
if (phrase_word_idx == phrase_word_length.size()) {
// If we reach the last word length of the phrase and no char is left
// for use, we found our solution.
bool valid = true;
for (auto cu : chars_in_phrase) {
if (cu != 0) {
valid = false;
break;
}
}
return valid;
}
// Find the first word with the length needed.
auto it = std::find_if(
words_to_use.begin(), words_to_use.end(),
[&phrase_word_length, phrase_word_idx](const std::string& str) {
return str.size() == phrase_word_length[phrase_word_idx];
});
// If not have the length needed (it's not possible in the actual algorithm,
// because we allow using
// the same word multiple times, if its only used once, could be necessary).
if (it == words_to_use.end() ||
it->size() != phrase_word_length[phrase_word_idx])
return false;
// Iterate throught the words with the same target length.
while (it != words_to_use.end() &&
it->size() == phrase_word_length[phrase_word_idx]) {
if (can_use_word(chars_in_phrase, *it)) {
phrase.push_back(*it);
// Continue searching the next word in the phrase
if (solve_phrase(chars_in_phrase, phrase_word_length, words_to_use,
phrase, phrase_word_idx + 1))
return true;
// If it reach dead end, revert the state of the used chars and
// continue with the next possible word.
phrase.pop_back();
for (unsigned int idx = 0; idx < it->size(); idx++) {
chars_in_phrase[(*it)[idx] - 'a']++;
}
}
it++;
}
return false;
}
int main() {
std::vector<std::string> words_to_use{
"crypt", "by", "my", "cysts", "glyph", "psych", "shyly",
"slyly", "try", "sylph", "tryst", "gypsy", "ply", "pry",
"shy", "sly", "spy", "thy", "cry", "sty", "glyphs",
"sylphs", "trysts", "crypts", "psychs", "sprly"};
std::string phrase =
"[YYY] [YYYYY] [YYYBC] [GHLLLM] [PPPRR] [RS] [SS] [SSTTT]";
std::vector<long> chars_in_phrase(26, 0);
std::vector<long> phrase_word_length;
// Initializing the char used in the phrase and the word length of the
// phrase
unsigned int begin_idx = 0;
for (unsigned int idx = 0; idx < phrase.size(); idx++) {
char c = phrase[idx];
if (c == '[') {
begin_idx = idx;
} else if (c == ']') {
phrase_word_length.push_back(idx - begin_idx - 1);
} else if (c != ' ') {
chars_in_phrase[c - 'A']++;
}
}
// Sorting the words by size.
std::sort(words_to_use.begin(), words_to_use.end(),
[](const std::string& left, const std::string& right) {
if (left.size() == right.size())
return left < right;
return left.size() < right.size();
});
std::vector<std::string> phrase_solved;
solve_phrase(chars_in_phrase, phrase_word_length, words_to_use,
phrase_solved);
for (auto p : phrase_solved) {
std::cout << p << " ";
}
std::cout << std::endl;
return 0;
}
得られた出力:pry crypt gypsy trysts shyly by my slyly