Дайте две строки s1 и s2, дайте алгоритм, чтобы найти все символы из S1, которые также есть в S2

Question

Пример:

S1: abcde S2: cdef

Ответ: cde

Answer 1

Разумно предположить, что набор символов небольшой и конечный по сравнению с потенциальной длиной строки. Так, например, обработка 8-битных символов (в псевдокоде примерно на C ++):

bool in_a[256] = { false };
bool in_b[256] = { false };
for (int i = 0; i < a.size(); ++i)
    in_a[a[i]] = true;
for (int i = 0; i < b.size(); ++i)
    in_b[b[i]] = true;
// and in_a and in_b
for (int i = 0; i < b.size(); ++i)
    if (in_a[i] && in_b[i])
    {
        std::cout << i;
        if (isprint(i)) std::cout << '\'' << (char)i << '\'';
        std::cout << ' ';
    }
std::cout << '\n';

Обратите внимание, что использование хеш-таблицы, а не массива, - огромная трата времени (если не обрабатывать, скажем, 32-битное символьное представление).

Ниже следует реализация упрощения, предложенного в комментарии Йордана. Это позволяет избежать последнего цикла с 0..255 и требует только один массив отслеживания. Порядок результатов не отсортирован.

#include <vector>
#include <iostream>

int main()
{
    std::string a = "abdcdefg";
    std::string b = "byfdz";
    bool track[256] = { false };
    for (int i = 0; i < a.size(); ++i)
        track[a[i]] = true;
    for (int i = 0; i < b.size(); ++i)
        if (track[b[i]])
        {
            track[b[i]] = false; // don't match again
            std::cout << (int)b[i];
            if (isprint(b[i])) std::cout << " \'" << (char)(b[i]) << "\'";
            std::cout << ' ';
        }
    std::cout << '\n';
}

Answer 2

Использовать какую-то структуру данных набора : заполнить набор каждым символом S1. Затем проверьте для каждого символа в S2, находится ли он в наборе.

В зависимости от реализации вставка и поиск в наборе обойдутся только в O (1).

Answer 3

В верхней части головы я разбил обе строки на массив символов и отсортировал их.Затем я бы прошел через один массив и для каждого символа проверил, был ли он в другом.Сортировка обоих массивов означает, что вам нужно пройти через каждый массив только один раз при получении результата.Я не уверен, что издержки сортировки делают его еще более эффективным.

Могут быть уместными следующие вещи:

1) повторяющиеся символы в строке - отклонены, потому что отключеныв верхней части головы я не мог придумать хороший эффективный способ отфильтровывать дубликаты.

2) Различные случаи могут хотеть считаться равными (например, А и А считаются одинаковыми) - не просилино таупер или тауэр решат это.

Answer 4

Сортируйте обе строки в одном и том же порядке, а затем линейно сканируйте обе последовательности одновременно, сравнивая каждый элемент, если он не совпадает, увеличивайте последовательность с помощью символа с более низким значением. Это должно быть O (N log N) в предположении.

Answer 5

Попробуйте сделать это в Python:

char_in_s2=''

for char in s1:

      if char in s2:
         char_in_s2=char_in_s2+char

print(char_in_s2)

Answer 6

Если вам известно количество уникальных символов, из которых состоят строки (например: если используются только символы нижнего регистра, то az означает 26 уникальных символов), то получите массив такого размера, используя символы в качестве индекса.Перебирайте каждую строку и для каждого из ее символов увеличивайте соответствующее расположение массива (скажем, вы нашли b, затем a [1] ++).В конце подсчитайте количество позиций массива, которые имеют значение 2. Конечно, это решение имеет большую сложность пространства.

Редактировать: подсчитать количество позиций массива, которые имеют 2 или более в качестве значения.(Спасибо Крису за то, что он указал на ошибку в предыдущем ответе)

Answer 7

Другой метод подсказывает мне сейчас ... В псевдокоде, поскольку его легче объяснить:

for each (character in stringA)
{
    charHashTable[character] = 1

}
for each (character in stringB)
{
    if (charHashTable[character]==1)
        if (!OutputArray.Contains(character))
            OutputArray.Add(character)
}

Я не на 100% уверен в характеристиках производительности, помещаемых в хэш-массивы, номне пришло в голову, что это может быть лучший способ эффективно найти, если символ находится в одном массиве, чем сортировать его и делать это таким образом.Если кто-то может прокомментировать преимущества этого метода в производительности по сравнению с сортировкой обеих строк, я был бы очень заинтересован.

Answer 8

var commonChars = S1.Intersect(S2);

РЕДАКТИРОВАТЬ: Это от System.Linq - и это алгоритм - это один, однострочный алгоритм. : -)

Answer 9

Используйте хэш-карту, где ключи - это символы первой строки, а значения - это int, начинающиеся с нуля.Затем просто найдите каждый символ из S2 и, если поиск выполнен успешно, увеличьте значение.Настройка карты хеш-функции - O (n), а каждый поиск - O (1).В худшем случае производительность составляет около O (2n), что эквивалентно O (n).

Просто для справки, вы можете использовать контейнер Boost unordered_map в реальном мире.

Answer 10

В ruby ​​алгоритм O (len (s1) + len (s2)) с использованием хеш-таблицы

require 'jcode'
def toto(s1, s2)
    contains={}
    s2.each_char { |x| contains[x]=1 }
    res=""
    s1.each_char do |x|
        if contains[x]==1
            res<<=x
        end
    end
    return res
end

puts toto("abcde","cdef")