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), whereN和Mare: word.size()and cont.size(). 我猜想即使是小尺寸的输入，它也至少快 100 倍。

于 2013-08-01T10:36:38.643 回答