Напишите функцию, которая сравнивает две строки и возвращает третью строку, содержащую только буквы, которые появляются в обоих

Question

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

    public string ReturnCommon(string firstString, string scndString)
    {
        StringBuilder newStb = new StringBuilder();
        if (firstString != null && scndString != null)
        {
            foreach (char ichar in firstString)
            {
                if (!newStb.ToString().Contains(ichar) && scndString.Contains(ichar))
                    newStb.Append(ichar);
            }
        }
        return newStb.ToString();
    }

Answer 1

Для альтернативного решения вы можете просмотреть строки как перечислимые и использовать Intersect(), например:

    public static string Common(string first, string second)
    {
        return new string((first.Intersect(second)).ToArray());
    }

Answer 2

Это хорошо для первого подхода, но вы можете сделать несколько улучшений, и есть небольшая ошибка.

• Если b содержит символ в a, который уже находится в c, вы повторите его.
• Чтобы избежать повторений, вы можете использовать Set для хранения символов, поскольку Set не будет иметь повторов.
• Сборка строк с конкатенацией += обычно неэффективна; рассмотрите возможность использования StringBuilder или аналогичного класса сборки строк.
• Ваши имена переменных не очень наглядны.
• Если a или b пусты, вам вообще не нужно ничего делать! Просто верните пустую строку.

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

Answer 3

Чтобы улучшить последнее предложение Джона Феминеллы, более быстрый, чем бинарный поиск (для любой достаточно длинной строки) будет поиск в хэш-наборе; или поиск в 256-элементном массиве логических значений, если это символы ASCII или UTF8 вместо символов UTF16.

• Создание пустого хэш-набора или пустого массива логических значений; назовите эту переменную found.
• Для каждого символа в первой строке либо добавьте символ в хэш-набор (но остерегайтесь дублирующихся символов в первой строке), или установите соответствующий элемент в массиве found в значение true; это займет линейное время O (n).
• Для каждого символа во второй строке проверьте, существует ли этот символ в хэш-наборе или является ли соответствующий элемент в массиве 'found' истинным: если найдено, добавьте символ в возвращаемую строку, а также удалите символ из hashset или очистите логический элемент в массиве, чтобы он не был найден снова (остерегайтесь дублирующихся символов во второй строке); это займет линейное время O (n).

Answer 4

Зависит от как долго будут входные строки, что такое буква и как должен выглядеть вывод (дубликаты). Есть несколько других подходов.

Например:

Если буквы являются просто [AZ] символами и каждая буква должна появляться только один раз в выходной строке, вы можете создайте отдельную строку (или таблицу символов) 'ABC ... XZ' (назовем это letters) и запустите for each loop over letters и проверьте обе входные строки для каждой буквы от letters.

Это дает 26 итераций цикла и , не более , тогда 52 вызывает из Contains() метода для каждой входной строки - независимо от длины входных строк .

Answer 5

Кажется, хорошо. Вы можете сделать пару оптимизаций в зависимости от языка, который вы используете:

• вы можете собрать буквы b в какую-то упорядоченную структуру (чтобы ускорить поиск), и если она не повторяется ... лучше (набор).
• вы можете использовать какой-то тип StrignBuilder (если это Java или .Net), чтобы не воссоздавать строку с каждой конкатенацией внутри цикла

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

Answer 6

Использование LINQ:

a.ToCharArray().Intersect<char>(b.ToCharArray())

Однако это чувствительно к регистру.

Answer 7

Вот мое решение на питоне. Если я не ошибаюсь, это должно занять линейное время O (n).

# Write a function f(a, b) which takes two character string arguments
# and returns a string containing only the characters found in both
# strings in the order of a. 
first_string = "attempt" 
second_string="tmay" #second string
result = []

#it's O(n) operation
for char in first_string:
   if char in second_string:
      if char not in result:
         result.append(char)

print result

результаты выглядят так:

['a', 't', 'm']

Answer 8

К вашему сведению: Вот код C / C ++:

/* Q: Write a function f(a, b) which takes two character string arguments
      and returns a string containing only the characters found in both
      strings in the order of a. */

#include <iostream>
#include <string>
#include <cstring>
#include <map>
using namespace std;

/* A: Unclear: repeated chars in string a? */
string CommonChars(const char* a, const char* b)
{
    string result("");

    if (!a || !b || !*a || !*b)
        return result;

    map<char, bool> hash;
    int len1 = strlen(a), len2 = strlen(b);

    for (int i = 0; i < len2; ++i)
        hash[b[i]] = true;

    for (int i = 0; i < len1; ++i)
    {
        map<char, bool>::iterator it = hash.find(a[i]);
        if (it != hash.end() && it->second)
        {
            result += a[i];
            hash[a[i]] = false; // OR:  hash.erase(it);
        }
    }

    return result;
}

int main()
{
    cout << CommonChars("abcdefgbx", "gcfcba") << endl;

    return 0;
}
/* Output:
abcfg
 */

Answer 9

Выглядит хорошо для меня, но, ради бога, человек - используйте некоторые описательные имена переменных !!