Превратите дубликаты в отдельные буквы в строке [закрыто]

MonkeyDluffy

9 августа 2021 в 05:09

116

-3

Нам будет задана строка s. Предположим, например, "creepfe". Что мы хотим сделать, так это удалить дубликаты и вместо этого добавить новую букву в этом месте, и новая буква должна быть отдельной буквой, доступной рядом с повторяющейся буквой в алфавитном порядке. Вот так:

creepfe to crefpfe -- первое e отличается, а второе e изменяется на f, которое отличается до этого.

crefpfe to crefpge -- вторая буква f заменяется на g, так как f у нас уже есть раньше.

crefpge в crefpgf -- так как e уже присутствует.

Теперь мы снова получили f-дубликат, поэтому измените его на crefpgg, который снова получил g-дубликат, так что, наконец, мы достигли «crefpgh», в котором все буквы разные.

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

Редактировать: да, заглавные буквы тоже считаются дубликатами. И длина строки ограничена 10-15, так что не беспокойтесь о том, что у вас закончится отдельная буква.

Источник

Поделиться Скопировать ссылку Скопировано

YHStan

9 августа 2021 в 05:14

а как же столицы? будет ли это считаться дубликатом?

MonkeyDluffy

9 августа 2021 в 05:16

Да, заглавные буквы учитываются при дублировании!

MBo

9 августа 2021 в 05:19

Кажется, это задача для наборов. Вы пытались использовать set для символов в строке?

MonkeyDluffy

9 августа 2021 в 05:22

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

YHStan

9 августа 2021 в 05:28

^ хорошо, set используется, потому что проверка того, была ли буква уже видна ранее ( contains() ), является постоянной временной сложностью O (1).

Ответы (2)

YHStan

9 августа 2021 в 06:18

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

public class tester {
    public static void main(String[] args){
        //Application.launch(testclass.class, args);
        String str = "creepFeZZ";

        System.out.println(processStr(str));

    }

    public static String processStr(String str){
        StringBuilder sb = new StringBuilder();
        HashSet<String> seen = new HashSet<>();

        insertStr(sb, seen, String.valueOf(str.charAt(0)));

        for (int i=1; i<str.length(); i++){
            char currentchar = str.charAt(i);
            char processedchar = goNext(seen, currentchar);
            insertStr(sb, seen, String.valueOf(processedchar));
        }

        //System.out.println(seen.toString());

        return sb.toString();
    }

    private static void insertStr(StringBuilder sb, HashSet seen, String str){
        seen.add(str.toLowerCase());
        sb.append(str);
    }

    private static char goNext(HashSet seen, char c){
        if (c>= 65 && c<=90){
            //if uppercase letter, check if contains lowercase version
            if (seen.contains(String.valueOf((char)(c+32)))){
                c = goNext(seen, (char)(c+1));
            }
            //any left shifting will overflow back to A
            return (char) ((c -(int) 'A') % 26 +(int) 'A');
        }else{
            //if lowercase letter, just check if contains
            if (seen.contains(String.valueOf((char)(c)))){
                c = goNext(seen, (char)(c+1));
            }
            //any left shifting will overflow back to a
            return (char)((c-(int) 'a') % 26 +(int) 'a');
        }
    }
}

Это дает вывод: crefpGhZA

Поделиться Скопировать ссылку Скопировано

MonkeyDluffy

9 августа 2021 в 06:29

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

HiEd

9 августа 2021 в 06:10

-1

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

String value = "C";
int charValue = value.charAt(0);
String next = String.valueOf( (char) (charValue + 1));
System.out.println(next);

Повторяйте процесс до тех пор, пока не будет больше дубликатов (есть цикл while, который прерывается, когда дубликатов больше нет)

Поделиться Скопировать ссылку Скопировано

MonkeyDluffy

9 августа 2021 в 06:17

Проблема в том, что если сгенерированные символы уже присутствуют в строке? Как и в шаге « crefpge to crefpgf -- так как e уже присутствует. Теперь мы снова получили дубликат f , поэтому измените его на crefpgg , который снова получил дубликат g , поэтому, наконец, мы достигли «crefpgh», в котором все буквы разные». Проверка дубликатов снова и снова и изменение снова и снова кажется более сложным, чем я думал. По сути, проблема заключается в том, чтобы напрямую генерировать следующий алфавит без какой-либо проверки, присутствует ли он уже в моем представлении.