Удалить повторяющиеся символы из 2 строк

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

private static String removeDup(String s1, String s2) {
    BitSet bitSet = new BitSet(26);
    char[] s1Chars = s1.toCharArray();

    for (char s1Char : s1Chars) {
        bitSet.set(s1Char);
    }

    char[] s2Chars = s2.toCharArray();
    StringBuilder sb = new StringBuilder();
    for (char s2Char : s2Chars) {
        if (bitSet.get(s2Char)) {
            //System.out.println("Duplicate " + s2Char);
        } else {
            sb.append(s2Char);
        }
    }

    return sb.toString();
}

Хотя этот метод работает, есть ли какой-то более лучший и оптимальный способ сделать это с точки зрения сложности времени и пространства? Спасибо

Например

  • Входные данные: "hello", "world"
  • Выход: wrd

1 ответ

Одна проблема с вашей реализацией состоит в том, что для нее требуется количество бит памяти, равное максимальному значению символа в строке, и работает только для символов BMP. Обратите внимание, что персонаж a на самом деле соответствует значению символа 97. Где вы выделяете BitSetвы передаете ему параметр размера 26, но это бессмысленно; однако значение 256 может дать небольшое увеличение производительности.

Если бы вы использовали это в строках, содержащих иероглифы CJK, вы могли бы потенциально использовать до 8 КБ хранилища с этим BitSet,

Если вместо этого вы используете разреженную таблицу поиска, такую ​​как Set<Character>Вы можете значительно снизить требования к хранилищу, но это увеличивает время выполнения с O (n) до O (n log n).

Другим возможным улучшением будет распараллеливание алгоритма. Однако добавление распараллеливания только ускорит его для очень больших строк и может значительно замедлить его для небольших строк. В java-8 это можно сделать так:

private static String removeDup(String s1, String s2) {
    Set<Integer> points = s1.codePoints().collect(Collectors.toSet());
    return s2.codePoints().parallel().filter(c->!points.contains(c))
        .collect(StringBuilder::new, StringBuilder::appendCodePoint,
            StringBuilder::append).toString();
}

Это также имеет преимущество работы с персонажами вне BMP.

Другие вопросы по тегам