这是有趣的，因为它是一个可能的面试问题，所以这将是很好的了解最有效的算法针对此问题。我想出了一个解决方案（包含其他人的解决方案的元素），需要一个地图＆LT;焦炭，INT＆GT; 存储从第一个字符串作为键字母和数字它们的出现为价值。然后，该算法通过查找在容器中的每个字母字符串，如果有已经在地图中的条目检查。如果是这样，减少它的值，直到它的零等;直到容器结束（失败），或直到地图是空的（成功）。

在这个算法的复杂度为O（n），O（N）是在最坏的情况下（失败）。

你知道一个更好的办法？

下面是我写的，测试和评价了code：

  //需要一个字，我们需要找到和容器，可能的字母吧
布尔stringExists（串词，串容器）{

    //成功最初是假的
    布尔成功= FALSE;

    //键=字符重新presenting信;一个字中值= INT =出现次数
    地图＆LT;焦炭，INT＆GT; wordMap;

    //通过单词的每个字母循环
    为（无符号​​I = 0; I＆LT; word.length（）;我++）{

        字符键= word.at（我）; //这封信保存为一个字符一个关键

        如果（wordMap.find（键）== wordMap.end（））//如果信中不存在地图...
            wordMap.insert（make_pair（键，1））; //它添加到地图为1的初始值

        其他
            wordMap.at（键）++; //否则，增加它的价值

    }

    的for（int i = 0; I＆LT; container.size（）及和放大器;！成功;我++）{

        字符键= container.at（我）;

        //如果发现
        如果（wordMap.find（键）！= wordMap.end（））{

            如果（wordMap.at（键）== 1）{//如果这是此键在地图的最后一次出现

                wordMap.erase（键）; //删除此对

                如果（wordMap.empty（））//所有的字母被发现在容器！
                    成功= TRUE; //这将停止循环运行

            }

            否则//否则，如果有这个键的多个值
                wordMap.at（键） - ; //递减计数

        }
    }

    返回成功;
}
 

解决方案

不要使用的std ::地图。通常它有 O（日志N）写的， O（日志N）访问。在写入和malloc调用。

有关字符您可以使用简单的 INT频率[256] 表（或 STD ::矢量，如果你愿意的话）。

 布尔stringExists（常量字符串和放大器;字，常量字符串和放大器;续）{
  INT频率[CHAR_MAX-CHAR_MIN + 1] = {0};
  对于（INT C：续）++频率[C-CHAR_MIN]。
  对于（INT C：字）如果（ - 频率[C-CHAR_MIN]℃下）返回false;
  返回true;
}
 

这code复杂性是 O（N + M），其中 N 和 M 是： word.size（）和 cont.size（） 。我猜想，这是甚至从小型的投入至少快100倍。

This is interesting because it's a possible interview question, so it would be good to know the most efficient algorithm for this problem. I came up with a solution (which contains elements of other people's solutions) that requires a map<char, int> to store letters from the first string as keys, and numbers of their occurrences as values. The algorithm then looks through each letter in the container string and checks if there's already an entry in the map. If so, decrement its value until it's zero and so on; until the container is finished (failure), or until the mapis empty (success).

The complexity of this algorithm is O(n), O(n) being the worst-case scenario (failure).

Do you know a better way?

Here is the code that I've written, tested and commented:

// 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;
}

Do not use std::map. Usually it has O(log N) write, and O(log N) access. And malloc call on write.

For char you can use simple int freq[256] table (or std::vector if you are so inclined).

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;
}

Complexity of this code is O(N + M), where N and M are: word.size() and cont.size(). And I would guess that it is at least 100 times faster even from small sized inputs.