0

到目前为止，我的 c++ 程序如下所示：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int i;
    int maxLet;
    const int NumWords = 26;
    const int NumPhrase = 8;
    string ele;
    string n[NumWords] = {
        "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"};
    vector<string> words(n, n + NumWords);
    vector<string> phrase(n, n + NumPhrase);
    for (i = 0; i < words.size(); i++) {
        cout << words.at(i) << endl;
        cout << words[i] << endl;
    }

    char aaaaa;
    cin >> aaaaa;
    return 0;
}

我需要创建一个类似于 [YYY] [YYYYY] [YYYBC] [GHLLLM] [PPPRR] [RS] [SS] [SSTTT] 的短语，其中字母全部打乱，括号表示单词的长度。本质上，我需要创建一个具有这些特定字长的词组，以及这些特定数量的字母，11 y's 1 b 1 c 1 g 1 h 3 L's 1 m 3 p's 3 r's 5 s's 3t's I've been pulling我的头发想弄清楚该怎么做。您的意见将不胜感激。

4

2 回答 2

1

由于您所有的单词模板（[...] 的集合）都是不同的，因此您只需计算每个此类元素的可能匹配项并将这些数字相乘。所以，让我们先写一个这样的函数：

bool isMatch(string templ, string word)
{
sort(templ.begin(), templ.end());
sort(word.begin(), word.end());
return templ==word;
}

long long countMatches(string templ, vector<string> const& dict)
{
long long ret=0;
for(int i = 0; i < dict.size(); i++)
  ret += isMatch(templ, dict[i]);
return ret;
}

long long finalAnswer(vector<string> const& templs, vector<string> const& dict)
{
 long long ans=1;
 for(int i=0; i<templs.size(); i++)
   ans*=countMatches(templs[i], dict);
 return ans;
}
于 2014-08-02T19:21:56.873 回答
0

因为问题陈述不可用，我假设：

  1. 短语的单词总共必须使用 in 内的总字符，[]但不是每个单词都使用[].
  2. 这句话必须完全使用里面的所有字符[]
  3. 您可以多次使用单词（可以轻松更新为仅使用一次单词）
  4. 要使用的单词以小写形式输入。
  5. 短语中使用的字符以大写形式输入。

代码（在 GCC 4.9.0 中使用 C++11 测试）：

#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

于 2014-08-02T21:00:22.110 回答