Поиск вариантов строки (только удаление, без транспонирования)

Question

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

helloo

Список вариантов будет следующим (разделены пробелом).

helloo hello heloo helo

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

// takes String with at most two consecutive characters of any character, 
// and returns an Iterable of all possible variants (e.g. hheello -> heello, hhello, ...)
private static Iterable<String> findAllVariants(String word) {
    StringBuilder variant = new StringBuilder(word);
    Queue<String> q = new LinkedList<String>();
    findAllVariants(word, variant, 0, q);
    return q;
}

// helper method
private static void findAllVariants(String word, StringBuilder variant, int currIndex, Queue<String> q) {
    if (currIndex == variant.length() - 1) q.add(variant.toString());

    for (int i = currIndex; i < variant.length() - 1; i++) {
        char thisChar = variant.charAt(i);
        char nextChar = variant.charAt(i+1);
        if (thisChar == nextChar) {
            // get all variants with repeat character
            findAllVariants(word, variant, i+1, q);

            // get all variants without repeat character;
            variant = variant.deleteCharAt(i);
            findAllVariants(word, variant, i, q);
        }
    }
}

Тем не менее, я получаю большое количество копий ответов, и ни одного другого. Когда я делаю свой алгоритм на бумаге, он кажется правильным. Что я делаю неправильно?

Answer 1

Нечто похожее на следующий код позволит вам получить все возможности (не забудьте добавить word сам при необходимости). Идея состоит в том, чтобы восстановить все возможности для удаления одного символа (например, hello результаты в ello hllo helo hell). Эти результаты, в свою очередь, могут быть использованы для получения возможности удаления двух символов (снова удалите один символ). В результате чего llo elo ell за ello и так далее...

List<String> getPossibilities(String word) {
    int removeChars = word.length() - 1;
    List<String> possibilities = new ArrayList();
    List<String> options = Arrays.asList(word);
    for(int i = 0; i <= removeChars; i++) {
        List<String> results = new ArrayList();
        for(String option : options) {
          for(String result : removeOneChar(option)) {
                if(!results.contains(result)) {
                    results.add(result);
                }
            }
        }
        possibilities.addAll(results);
        options = results;
    }
    return possibilities;
}

private static List<String> removeOneChar(String word) {
    List<String> results = new ArrayList();
    for(int i = 0; i < word.length(); i++) {
        int secondPart = i + 2;
        if(secondPart <= word.length()) {
            results.add(
                    word.substring(0, i) 
                    + word.substring(i + 1, word.length()));
        }
        else {
            results.add(
                    word.substring(0, i));
        }
    }
    return results;
}

Обратите внимание на if(!contains(result)) для того, чтобы предотвратить любые дубликаты.

Обратите внимание, я использовал substring() чтобы достичь этого, вы подходите с removeCharAt() это еще один хороший вариант. Вы можете запустить несколько тестов, чтобы увидеть, какие из них лучше, чтобы решить, какой из них использовать. Обратите внимание, что использование последнего может устранить необходимость if в private метод.

Answer 2

Я бы использовал совсем другой алгоритм: я бы нашел все повторения (ll) (oo) (lll) (ooo) и т. Д., Сохранил массив, описывающий их позиции в тексте, и количество символов на каждое повторение.
например, массив A =
[Л | 2]
[О | 2]
,
,
,

Затем я бы сказал, что есть второй массив с начальным счетом ноль, и увеличу количество и выведу все перестановки:

Массив B =
[Л | 1]
[О | 1]
==> печатает привет

Шаг 2: (увеличение количества)
B =
[Л | 2]
[О | 1]
==> печатает привет

Шаг 3:
B =
[l | 3] ==> больше, чем max, поэтому установите его на 0 и увеличьте вторую ячейку, чтобы она стала:
B =
[Л | 1]
[О | 2]
==> печатает Heloo

Шаг 4: (снова увеличить первый элемент)
[l |2] ==> не больше, чем max, поэтому переполнения нет, поэтому сохраняйте его
[О | 2]
==> печатает привет