Я решаю проблему с LeetCode, но никто еще не смог объяснить мою проблему.
Проблема как таковая:
Учитывая произвольную строку примечания с требованием выкупа и другую строку, содержащую буквы из всех журналов, напишите функцию, которая будет возвращать true, если примечание с требованием выкупа может быть построено из журналов; в противном случае он вернет false.
Каждая буква в строке журнала может использоваться только один раз в вашей записке с требованием выкупа.
Примечание:
Вы можете предположить, что обе строки содержат только строчные буквы.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
Мой код (который занимает 32 мс):
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if(ransomNote.size() > magazine.size()) return false;
unordered_map<char, int> m;
for(int i = 0; i < magazine.size(); i++)
m[magazine[i]]++;
for(int i = 0; i < ransomNote.size(); i++)
{
if(m[ransomNote[i]] <= 0) return false;
m[ransomNote[i]]--;
}
return true;
}
};
Код (который я не знаю, почему быстрее - занимает 19 мс):
bool canConstruct(string ransomNote, string magazine) {
int lettersLeft = ransomNote.size(); // Remaining # of letters to be found in magazine
int arr[26] = {0};
for (int j = 0; j < ransomNote.size(); j++) {
arr[ransomNote[j] - 'a']++; // letter - 'a' gives a value of 0 - 25 for each lower case letter a-z
}
int i = 0;
while (i < magazine.size() && lettersLeft > 0) {
if (arr[magazine[i] - 'a'] > 0) {
arr[magazine[i] - 'a']--;
lettersLeft--;
}
i++;
}
if (lettersLeft == 0) {
return true;
} else {
return false;
}
}
Оба они имеют одинаковую сложность и используют одну и ту же структуру для решения проблемы, но я не понимаю, почему один занимает почти вдвое больше времени, чем другой. Время запроса вектора - O (1), но то же самое для unordered_map. Та же история с добавлением записи / ключа к любому из них.
Пожалуйста, кто-нибудь может объяснить, почему время выполнения так сильно меняется?