Добавить элементы в вектор рекурсивно - PullRequest
Новая
       23

Добавить элементы в вектор рекурсивно

1 голос
/ 14 мая 2011

Я пытаюсь создать рекурсивную функцию, которая выводит вектор строк, который содержит все возможные комбинации слов (при сохранении порядка букв) данной строки.По сути, это основа программы автокоррекции, которая производит эффекты, аналогичные iPhone. 

vector<string> allPossibleWords(string str, vector<vector<char> > & adjacentKeys)
{
  vector<string> words;

  cout << str << endl;

  if (str.length() == 0)
  {
    return words;
  }

  char firstLetter = str[0];
  string restOf = str.substr(1, str.length() - 1);
  int position = position_in_vector(firstLetter);

  for (int i = 0; i < adjacentKeys[position].size(); i++) 
  {
    string temp(1, adjacentKeys[position][i]);
    words.push_back(temp);
  }

  //allPossibleWords(restOf, adjacentKeys);
}

int position_in_vector(char letter)
{
  return (letter % 97);
}

Например, если str равно "yp", выводом должен быть вектор, содержащий значения {"yp", "tp", "gp", "hp", "up", "yo", "to", "go", "ho", "uo", "yl", "tl", "gl"," hl "," ul "}.Если str равно "y", выводом должен быть вектор, содержащий значения {"y", "t", "g", "h", "u"}.

26 векторов, хранящихся в соседних ключахсодержать буквы рядом с буквой, которая хранится в первой позиции вектора. 

a   qwsz
b   vghjn
c   xdfgv
d   zserfcx
//and so on

Я застрял с этой функцией и не могу понять, как рекурсивно построить этот вектор.

Ответы [ 2 ]

1 голос
/ 14 мая 2011

(Обновление: 21:30 по Гринвичу, воскресенье: я значительно изменил свой ответ. Я думаю, что теперь это работает.)

Вот полная программа. Я думаю, что есть и другие изменения, но я стараюсь придерживаться духа вашего первоначального решения. Важно вернуть одно пустое слово, когда str.length()==0. 

#include <vector>
#include <iostream>
using namespace std;


vector<string> allPossibleWords(string str, vector<vector<char> > & adjacentKeys)
{
        vector<string> words;

        // cout << "str=" << str << endl;

        if (str.length() == 0)
        {
                words.push_back("");
                return words;
        }

        char firstLetter = str[0];
        // cout << "firstLetter=" << firstLetter << endl;
        int positionInAdjacentKeys = 0;
        while(positionInAdjacentKeys < adjacentKeys.size() && adjacentKeys.at(positionInAdjacentKeys).front() != firstLetter) {
                ++ positionInAdjacentKeys;
        }
        vector<char> & adjacent = adjacentKeys.at(positionInAdjacentKeys);

        string restOf = str.substr(1, str.length() - 1);
        // cout << firstLetter << ":" << restOf << endl;

        // int position = position_in_vector(firstLetter);

        vector<string> recursiveWords = allPossibleWords(restOf, adjacentKeys);

        for (int i = 0; i < adjacent.size(); i++)
        {
                const string temp(1, adjacent[i]);
                // cout << "  temp=" << temp << endl;
                for(vector<string>::const_iterator i = recursiveWords.begin(); i != recursiveWords.end(); i++)
                {
                        // cout << "new word=" <<  temp + *i << endl;
                        words.push_back(temp + *i);
                }
        }
        return  words;
}


int main() {
        vector<vector<char> > adj;
        vector<char> v1;
        v1.clear();
        v1.push_back('p');
        v1.push_back('o');
        v1.push_back('l');
        adj.push_back(v1);
        v1.clear();
        v1.push_back('y');
        v1.push_back('t');
        v1.push_back('g');
        v1.push_back('h');
        v1.push_back('u');
        adj.push_back(v1);
        adj.push_back(v1);

        vector<string> words = allPossibleWords("yp", adj);

        for(vector<string> :: const_iterator i = words.begin(); i != words.end(); i++) {
                cout << *i << endl;
        }
}

Возвращение

0 голосов
/ 15 мая 2011

Может как то так?Я не проверял это, потому что у меня нет твоей adjacentKeys матрицы.Возможно, его можно немного оптимизировать, но я не думаю, что этот подход будет хорошо масштабироваться вообще.

Я бы предложил атаковать проблему под другим углом, возможно, сохраняя ваш словарь в каком-то виде K-арное дерево , и с несколькими указателями, идущими по дереву, следуя ветвям, основанным на вашей матрице смежности.Это остановит генерацию недопустимых слов (и последующие поиски для проверки правильности), поскольку ветви будут существовать только там, где существуют допустимые слова. 

using namespace std;

void allPossibleWordsHelper(const string& str, 
                            string::size_type index,
                            const vector<vector<char> >& adjacentKeys, 
                            vector<string>& results)
{
    if (str.length() == 0)
    {
        return;
    }

    std::string head = (index > 0) ? str.substr(0, index) : "";
    std::string tail = (index < str.length() - 1) ? str.substr(index + 1) : "";

    vector<string> possibleHeads;
    string::size_type headIndex = (str.length() - index) / 2;
    allPossibleWordsHelper(head, headIndex, adjacentKeys, possibleHeads);

    vector<string> possibleTails;
    allPossibleWordsHelper(tail, index + headIndex, adjacentKeys, possibleTails);

    int pos = str[index] - 'a';

    vector<string>::const_iterator headi;
    vector<string>::const_iterator headi_end = possibleHeads.end();

    vector<string>::const_iterator taili;
    vector<string>::const_iterator taili_end = possibleTails.end();

    vector<char>::const_iterator aki;
    vector<char>::const_iterator aki_end = adjacentKeys[pos].end();

    for(headi = possibleHeads.begin(); headi != headi_end; ++headi)
    {
        for (aki = adjacentKeys[pos].begin(); aki != aki_end; ++aki)
        {
            for (taili = possibleTails.begin(); taili != taili_end; ++taili)
            {
                string suggestedWord = *headi + *aki + *taili;

                results.push_back(suggestedWord);
            }
        }
    }
}
...