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

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) и т. Д., Сохранил массив, описывающий их позиции в тексте, и количество символов в каждое повторение.
Массив например А =
[л | 2]
[о | 2]
.
.
.

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

массива B =
[л | 1]
[о | 1]
==> печатает HELO

Шаг 2: (количество приращения)
В =
[L | 2]
[о | 1]
==> печатает привет

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

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