big o — обзор кода, C ++, метод Anagram

Question

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

0

anagram big-o c++review

Решение

Другие решения

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

3

Уже есть стандартный алгоритм 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 не очень хороший подход, потому что исходные строки будут изменены, или вы должны передать их функции по значению.

1

Источник

Accepted Answer

Это более эффективно, как правило,

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

5