Удалить повторяющиеся символы из 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.