1

次の Trie 構造体を使用します。

struct Trie{
    char letter;
    bool eow;
    Trie *letters[26];
};

次のコードを使用して、トライからアルファベット順に単語をベクトルに抽出しています。

void getWords(const TrieNode& data, vector<string> &words, string acc)
{
  if (data.eow)
    words.push_back(acc);

  for (int i = 0; i < 26; i++) {
    if (data.letters[i] != NULL)
      getWords(*(data.letters[i]), words, acc + data.letters[i]->letter);
  }
}

再帰せずに反復のみを使用してこれを行う方法があるかどうか疑問に思っていましたか? これを反復のみで実装しようとしていますが、ループを使用して、トライ内の各レイヤーのすべての文字をチェックする方法が思いつきません。助言がありますか？

4

1 に答える 1

0 
struct State {
  const TrieNode* data;
  string acc;
  int index;
  State( ... ): ... {} // element-wise constructor, left as an exercise
};

std::vector<string> getWords( const TrieNode* root )
{
  std::vector<string> retval;
  std::vector<State> states;
  states.push_back( State( root, string(), 0 ) );
  while (!states.empty())
  {
    State s = states.back();
    states.pop_back();
    if (s.data->eow)
    {
      retval.push_back( s.acc );
      continue;
    }
    if (s.index >= 26)
      continue;
    states.push_back( State( s.data, s.acc, s.index+1 ) );
    if (s.letters[s.index])
    {
      states.push_back( State( s.letters[s.index], s.acc + s.letters[s.index]->letter, 0 ) );
    }
  }
  return std::move(retval);
};

状態は、再帰的に追跡したものとほぼ同じデータを追跡する明示的なスタックです。再帰関数と同じ順序で要素にアクセスできたと思いますが、それは実際には問題ではありません。

上記のコードは記述されており、テストされていないことに注意してください。私は怠惰なので、Stateの要素ごとのコンストラクターを記述しなければなりません。

于 2012-10-27T20:22:26.887 に答える