Подсчитать количество разных символов между двумя строками одинаковой длины

Question

У меня есть две строки одинаковой длины. Каждая строка содержит цифры от «1» до «9».

Я хочу вычислить количество индексов, где символ в этом индексе одинаков между двумя строками.

Пример:

A = "1322113" and
B = "2312213" 

тогда выходные данные должны быть равны 4, поскольку символы в 1-м, 3-м, 5-м и 6-м индексе одинаковы (с учетом индексации на основе 0).

Я знаю о наивном решении итерации и проверки {O (п)}. Есть ли какая-нибудь библиотека или методика, которая может дать мне больше времени?

Answer 1

Вы не можете получить лучшую сложность, чем размер ввода, в этом случае N символов. Поскольку вам необходимо проверить все N символов (поскольку каждый из них может быть потенциальным решением), линейное решение O (N) проверки всех из них уже является оптимальным.

Надеюсь, это поможет.

Answer 2

Если вы хотите получить лучшие результаты, то вам следует рассмотреть различные подходы для хранения строки. Первая оптимизация, которую я вижу, состоит в том, чтобы сохранить строку как кусочки чисел. Затем вы можете перебирать такие числа и сравнивать их (если числа малы, вы можете использовать предварительно вычисленную таблицу результатов). Преимущества такого подхода слишком расплывчаты (сложность O (N) станет (O (N / постоянная) ~ O (N)). Но в образовательных целях вы можете попытаться улучшить алгоритм

Answer 3

Оптимальным решением является O (n), потому что в любом случае вы должны пройти обе строки, чтобы применить операцию к соответствующим символам или проверить результат примененной операции к строкам.

Что касается Конкретное решение задачи я могу предложить использовать стандартный алгоритм std::inner_;product.

Например

#include <iostream>
#include <string>
#include <functional>
#include <iterator>
#include <numeric>

int main() 
{
    std::string s1 = "1322113";
    std::string s2 = "2312213";

    auto n = std::inner_product( std::begin( s1 ), std::end( s1 ),
                                 std::begin( s2 ),
                                 size_t( 0 ),
                                 std::plus<>(),
                                 std::equal_to<>() );

    std::cout << "n = " << n << '\n';

    return 0;
}

Выходные данные программы:

n = 4

Если вы хотите посчитать количество неравных символов в одинаковых позициях, тогда вместо объекта функции std::equal_to используйте std::not_equal_to