5

嘿，我目前有这个代码。它让用户将字符串输入到一个数组中，限制为 5。我计划使用该数组然后从该数组中形成单词。我怎样才能做到这一点？

    const int row = 5;
    char array[row];
    char count = 0;
    char letter;
    while (count < 5)
    {
        cout << "Enter a letter: ";
        cin >> letter;
        array[count] = letter;
        count++;
    }
    cout << "Letter inputed" << endl;
    for (count = 0; count < 5; count++)
    {
        cout << array[count] << " " <<  endl;
    }
    system("pause");
4

3 回答 3

3

这里有一个提示可以让你走上正确的道路：甚至不要考虑使用std::next_permutation，除非这是你只会使用一次或两次的东西（甚至可能不会，因为它实际上比正确地完成工作更复杂）。

使用std::next_permutation，您的函数将约为 N! 比必要的1慢几倍——在 5 个字母的情况下，这将慢 120 倍，如果你使用更长的单词，它会很快变得更糟（例如，对于 10 个字母，它超过 350 万）。

相反，从预处理你的字典开始。代替 a std::set<std::string>of 单词，创建一个std::map<std::string, std::vector<string>>(or std::unordered_map，尽管英语的单词很少，这可能不会产生巨大的影响)。当您从字典中读取一个单词时，创建该字符串的排序版本。使用它作为键，并将单词的原始版本推送到该键的向量上。

然后，当您从用户那里得到一个单词时，对其进行排序，在地图中查找，相关的向量将包含可以从这些字母创建的每个单词（来自您的字典）。

1. 如果你使用std::map代替std::unordered_map，那应该是类似的N!/(log N)，但N!增长如此之快和log N增长如此缓慢以至于差异可以忽略不计（如果你得到的 N 足够大以至于 log N = 3，N! 将如此之大以至于 N! /log N 个计算步骤...好吧，你开始进入宇宙学问题，比如宇宙是否会在那之前死于热死（答案似乎是“是的，可能”）。

于 2013-10-24T16:07:13.003 回答
2

这里有一个提示，可以帮助您入门。标准库中有一个名为std::next_permutation. 假设您有要检查的单词字典，可能的解决方案可能如下所示：

std::sort(array, array + row);
do {
    // Check if array is a word.
} while (std::next_permutation(array, array + row));

这将循环遍历字母的每个排列。现在由您来验证它是否是一个有效的单词。

于 2013-10-24T15:37:33.877 回答
1

该解决方案使用关联数组将单词的排序字母映射到具有此类排序字母的单词。因此，可以通过在地图中进行一次查找来获得答案，这需要渐近O(log N)时间，其中 N 是您的字典的大小。

创建一个名为dic.txt. 如果您正在使用Visual Studio它，它应该与您的*.cpp文件位于同一目录中。将几个单词以“一行中的单词”格式放入其中。试试下面的代码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

int main() {
    // Dictionary file is in a "word in a row" format
    map< string, vector<string> > dictionary;
    ifstream dictionary_file("dic.txt");
    if (!dictionary_file.good()) {
        cout << "File doesn't exist" << endl;
        return 0;
    }
    string word;
    while (dictionary_file >> word) {
        string key = word;
        sort(key.begin(), key.end());
        dictionary[key].push_back(word);
    }

    // Read the letters
    string letters;
    cin >> letters;
    if (letters.size() > 5) {
        cout << "Too much letters" << endl;
        return 0;
    }

    // Sort the letters
    sort(letters.begin(), letters.end());

    // Output the answers
    vector<string> & ret = dictionary[letters];
    for (size_t i = 0, ilen = ret.size(); i < ilen; ++i) {
        cout << ret[i] << endl;
    }
}

提到这样的解决方案关心您的字母所在的情况。如果您不需要它，您可以strtolower在将单词添加到字典之前和对字母进行排序之前添加对函数的调用（从 PHP 获取该名称） .

string strtolowers(string const & word) {
    string ret = word;
    transform(ret.begin(), ret.end(), ret.begin(), tolower);
    return ret;
}

您需要添加<cctype>标题才能使此功能正常工作。

于 2013-10-24T15:48:27.213 回答