Как использовать отдельные буквы для форматирования слов

Question

Эй У меня есть этот код. Он позволяет пользователю вводить строки в массив с пределом 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"); 

Answer 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> заголовок для работы этой функции.

Answer 2

Вот вам подсказка, чтобы вы начали. В стандартной библиотеке есть функция std::next_permutation. Если у вас есть словарь слов, чтобы проверить против, возможное решение может выглядеть следующим образом:

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

Это будет цикл через все перестановки букв. Теперь вам нужно проверить, что это действительное слово.

Answer 3

Вот подсказка, чтобы вы начали на правильном пути: не даже рассматривать с помощью std::next_permutation, если это не то, что вы будете только когда-либо использовать один или два раза (и, возможно, даже не то, потому что это на самом деле более сложная чем выполнение права на работу).

Используя std::next_permutation, ваша функция будет приблизительно N! раз медленнее, чем необходимо - в случае 5 букв, которые будут в 120 раз медленнее, и если вы когда-нибудь будете использовать более длинные слова, это будет очень быстро очень быстро (например, для 10 букв это более 3,5 млн).

Вместо этого начните с предварительной обработки словаря. Вместо std::set<std::string> слов создайте std::map<std::string, std::vector<string>> (или std::unordered_map, хотя на английском языке достаточно слов, которые, вероятно, не будут иметь большого значения). Когда вы прочитаете слово из словаря, создайте отсортированную версию этой строки. Используйте это как ключ и нажмите исходную версию слова на вектор для этого ключа.

Затем, когда вы получаете слово от пользователя, сортируйте его, посмотрите, что на карте, и связанный вектор будет содержать каждое слово (из вашего словаря), которое может быть создано из этих букв.

---

_{1.Если вы используете std::map вместо std::unordered_map, это должно быть чем-то вроде N!/(log N), но N! растет так быстро, и log N растет так медленно, что это различие незначительно (если вы получите N достаточно большим, чтобы log N = 3, N! Будет настолько большим что N!/log N шагов вычисления ... ну, вы начинаете входить в вопросы космологии, например, будет ли вселенная умерла от смерти от жары до этого (на что ответ кажется «да, возможно»).}