Удаление последовательных дубликатов из строки рекурсивно проваливает выборочные тестовые случаи

Question

Таким образом, наша задача - рекурсивно удалять дубликаты из заданной строки. Например -

Входные данные: aabccba

Выходные данные: abcba

Мой код работал отлично для этого ввода и 4 из 6 других тестовых случаев. Из этих двух один дает ошибку времени выполнения, а другой говорит, что мой код дает неправильный ответ. Может кто-нибудь сказать мне, как я могу это исправить?

    public static String removeCons(String s) {
    if(s.length() == 1) return s;

    String ans = "";

    String rest = "";

    if(s.charAt(0) == s.charAt(1)) {
        ans += s.charAt(0);
        rest = removeCons(s.substring(2));
    }
    else {
        ans += s.charAt(0);
        rest = removeCons(s.substring(1));
    }

    return ans+rest;
}

Answer 1

Попробуйте aaab и произойдет сбой (возвращает aab).

Когда первые два символа совпадают, вы оставляете первый и пропускаете второй, не проверяя, если третий ( и on) также одинаковы.

Вместо этого пропустите первое и рекурсивно начните со второго, т. е.

if(s.charAt(0) == s.charAt(1)) {
    rest = removeCons(s.substring(1));
}
...

Затем метод можно изменить на:

public static String removeCons(String s) {
    if (s.length() <= 1) // fixed to handle empty string too
        return s;
    String ans = removeCons(s.substring(1));
    if (s.charAt(0) != s.charAt(1))
        ans = s.charAt(0) + ans;
    return ans;
}

Answer 2

В дополнение к ответу Андреаса вы можете написать вкратце так:

public static String removeCons(String s){
    if (s.length() <= 1) return s;

    if (s.charAt(0) == s.charAt(1)) return removeCons(s.substring(1));

    return s.charAt(0) + removeCons(s.substring(1));
}

Answer 3

Я предоставлю вам мой вариант и рекурсивный вариант.

    import java.util.HashSet;
import java.util.Set;

public class RemoveDupes {



    public static String removeCons(String s) {
        StringBuilder sb = new StringBuilder();
        Set<Character> chars = new HashSet();
        for (char c : s.toCharArray()) {
            if(!chars.contains(Character.valueOf(c))){
                sb.append(c);
                chars.add(Character.valueOf(c));
            }
        }
        return sb.toString();
    }



    public static String removeConsRecursive(String s) {
        if(s.length() < 2){
            return s;
        }
        String firstLetter = s.substring(0,1);
        String sanitized = s.substring(1).replaceAll(firstLetter,"");
        return firstLetter + removeConsRecursive(sanitized);
    }

    public static void main(String... args){
        System.out.println(removeCons("sasslaereso"));
        System.out.println(removeConsRecursive("sasslaereso"));
    }

}