big o — обзор кода, C ++, метод Anagram
Я занимаюсь практическими вопросами из книги «Взлом интервью», и хотел, чтобы некоторые люди просмотрели мой код на предмет ошибок и оптимизаций. Любая обратная связь будет принята с благодарностью.
Вопрос: Напишите метод, чтобы решить, являются ли две строки анаграммами или нет.
/*
Time complexity: O(n^2)
Space complexity: O(n)
*/
bool IsAnagram(std::string str1, std::string str2)
{
if(str1.length() != str2.length())
return false;
for(int i = 0; i < str1.length();i++)
{
bool found = false;
int j = 0;
while(!found && j < str2.length())
{
if(str1[i] == str2[j])
{
found = true;
str2[j] = NULL;
}
j++;
}
if(!found)
return false;
}
return true;
}
Решение
Это более эффективно, как правило,
#include <iostream>
#include <string>
#include <algorithm>
bool IsAnagram(std::string& str1, std::string& str2)
{
if(str1.length() != str2.length())
return false;
std::sort(str1.begin(), str1.end());
std::sort(str2.begin(), str2.end());
return str1.compare(str2) == 0;
}
int main(int argc, char* argv[])
{
std::string an1("army");
std::string an2("mary");
if(IsAnagram(an1, an2))
std::cout << "Hooray!\n";
return 0;
}
Для тех, кому не нравятся мутирующие строки, возможно, это лучший вариант. Может удалить ссылку на параметры 1 и 2 или сделать копию внутри функции, как здесь. Таким образом, параметры могут быть постоянными.
bool IsAnagram2(const std::string& str1, const std::string& str2)
{
if(str1.length() != str2.length())
return false;
std::string cpy1(str1), cpy2(str2);
std::sort(cpy1.begin(), cpy1.end());
std::sort(cpy2.begin(), cpy2.end());
return cpy1.compare(cpy2) == 0;
}
Другие решения
O(n) алгоритм. Вместо сортировки (которая O(n lg n)), подсчитайте вхождения символов в s1 и сравните их с вхождениями символов в s2.
#include <string>
#include <iostream>
#include <limits>
bool IsAnagram(const std::string& s1, const std::string& s2)
{
if (s1.size() != s2.size()) {
return false;
}
int count[std::numeric_limits<char>::max() + (std::size_t)1] = {};
for (auto c : s1) {
count[c]++;
}
for (auto c : s2) {
if (!count[c]) {
return false;
}
count[c]--;
}
return true;
}
int main(int argc, char **argv)
{
std::cout << IsAnagram(argv[1], argv[2]) << std::endl;
return 0;
}
Уже есть стандартный алгоритм std::is_permutation что позволяет просто выполнить задачу
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>int main()
{
std::string s( "aab" );
std::string t( "aba" );
std::cout << std::boolalpha
<< ( s.size() == t.size() &&
std::is_permutation( s.begin(), s.end(), t.begin() ) )
<< std::endl;
return 0;
}
Выход
true
Так что все, что вам нужно, это посмотреть, как реализован алгоритм. 🙂
Если вы хотите отдельную функцию, то она будет выглядеть так
bool IsAnagram( const std::string &s1, const std::string &s2 )
{
return s1.size() == s2.size() &&
std::is_permutation( s1.begin(), s1.end(), s2.begin() );
}
Использовать std::sort не очень хороший подход, потому что исходные строки будут изменены, или вы должны передать их функции по значению.