1

これは面接での質問の可能性があるので興味深いので、この問題に対する最も効率的なアルゴリズムを知っておくとよいでしょう。map<char, int>最初の文字列の文字をキーとして格納し、その出現回数を値として格納する必要があるソリューション (他の人のソリューションの要素を含む) を思いつきました。次に、アルゴリズムはcontainer文字列内の各文字を調べて、マップに既にエントリがあるかどうかを確認します。もしそうなら、それがゼロになるまでその値を減らします。が完了するまでcontainer(失敗)、またはmapが空になるまで (成功)。

このアルゴリズムの複雑さは O(n) で、O(n) は最悪のシナリオ (失敗) です。

もっと良い方法を知っていますか？

私が書いて、テストして、コメントしたコードは次のとおりです。

// takes a word we need to find, and the container that might the letters for it
bool stringExists(string word, string container) {

    // success is initially false
    bool success = false;       

    // key = char representing a letter; value = int = number of occurrences within a word
    map<char, int> wordMap;     

    // loop through each letter in the word
    for (unsigned i = 0; i < word.length(); i++) {

        char key = word.at(i); // save this letter as a "key" in a char

        if (wordMap.find(key) == wordMap.end())     // if letter doesn't exist in the map...
            wordMap.insert(make_pair(key, 1));      // add it to the map with initial value of 1

        else
            wordMap.at(key)++;                      // otherwise, increment its value

    }

    for (int i = 0; i < container.size() && !success; i++) {

        char key = container.at(i);

        // if found
        if (wordMap.find(key) != wordMap.end()) {

            if (wordMap.at(key) == 1) { // if this is the last occurrence of this key in map 

                wordMap.erase(key);     // remove this pair

                if (wordMap.empty())    // all the letters were found in the container!
                    success = true;     // this will stop the for loop from running

            }

            else                        // else, if there are more values of this key
                wordMap.at(key)--;      // decrement the count

        }
    }

    return success;
}
4

1 に答える 1

4

使用しないでくださいstd::map。通常、O(log N)書き込みとO(log N)アクセスがあります。そして、書き込み時に malloc を呼び出します。

charシンプルなint freq[256]テーブルを使用できます (または、そのstd::vector傾向がある場合)。

bool stringExists(const string& word, const string& cont) {
  int freq[CHAR_MAX-CHAR_MIN+1]={0};
  for (int c: cont) ++freq[c-CHAR_MIN];
  for (int c: word) if(--freq[c-CHAR_MIN]<0)  return false;
  return true;
}

このコードの複雑さはO(N + M)、 、 where 、NおよびMです。また、小さなサイズの入力からでも、少なくとも 100 倍高速であると推測できます。word.size()cont.size()

于 2013-08-01T10:36:38.643 に答える