c++ - 是否有更好(更有效)的方法来查找是否可以从另一个字符串的字符形成一个字符串？

Question

这很有趣，因为它可能是一个面试问题，所以最好知道解决这个问题的最有效算法。我提出了一个需要 map<char, int> 的解决方案(其中包含其他人解决方案的元素)将第一个字符串中的字母存储为键，将它们出现的次数存储为值。然后算法会查看 container 中的每个字母。字符串并检查 map 中是否已有条目。如果是这样，将其值递减直到为零，依此类推；直到 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;
}

Answer 1

不要使用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)，其中N和M是:word.size() 和 cont.size()。而且我猜想即使是小规模的输入，它也至少快 100 倍。