Рекурсивная строковая функция (Java)

Question

Я пытаюсь разработать функцию, которая по существу выполняет следующие действия:

String s = "BLAH";

сохранить в массиве следующее: вздор ла ба BLH бла кипа ба ЬН ах аль

Так что в основном я вычитал каждую букву из нее по одному. Затем вычитайте комбинацию из двух букв за раз, пока не останется 2 символа. Храните каждое из этих поколений в массиве.

Надеюсь, это имеет смысл,

Джейк

Answer 1

Как ты получил «Ал»? Они тоже перепутали?

Я бы создал HashSet для хранения всех перестановок и передал его рекурсивному методу.

void foo(HastSet<String> set, String string) {
    if (string.length < 2) // base case
        return
    else {
        // add the string to the hashset
        set.add(string);

        // go through each character
        for (int i = 0; i < string.length; i++) {
            String newString = s.substring(0,i)+s.substring(i+1);
            foo(set, newString);
        }
    }
}

Это если ты заботишься об уникальности. Если нет, вы можете использовать вектор. В любом случае вы можете использовать toArray, чтобы вернуть свой массив.

Answer 2

Это оптимизация ответа @ voodoogiant. По сути, я хочу отложить задачу построения слова до базового варианта рекурсии. Таким образом, вы можете использовать StringBuilder для создания слова. Поэтому рекурсия в основном включает и выключает биты логического массива, которые говорят, нужно ли использовать определенную букву в следующем слове.

Я давно не писал java-код, так что извините, если что-то не скомпилируется.

void buildWords(String baseWord, boolean[] usedLetters, HashSet<String> words, int index){
    if (index == baseWord.length()){
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < index; i++){
            if (usedLetters[i])
                builder.append(baseWord.characterAt(i));
        }
        words.add(builder.toString());
    }
    else{
        usedLetters[index] = true;
        buildWords(baseWord, usedLetters, words, index+1);
        usedLetters[index] = false;
        buildWords(baseWord, usedLetters, words, index+1);
    }
}

Вещи, которые вы должны знать:

1. Это может создать пустую строку (если все позиции массива ложны).
2. Это может создавать повторяющиеся слова (если baseWord имеет последовательные повторяющиеся символы), и я не помню, генерирует ли HashSet исключение при добавлении повторяющихся ключей.
3. Не помню, если метод StringBuilder, который добавляет символ в конец, называется "добавлением", но вы поняли идею.
4. Не помню, если метод StringBuilder, который выводит построенную строку, является "toString", но вы также поняли идею.

Answer 3

Для этого вам не нужна рекурсия. Вот итерационный алгоритм:

    String master = "abcd";
    final int L = master.length();

    List<String> list = new ArrayList<String>();
    list.add(master);
    Set<String> current = new HashSet<String>(list);
    for (int i = L-1; i >= 2; i--) {
        Set<String> next = new HashSet<String>();
        for (String s : current) {
            for (int k = 0; k < s.length(); k++) {
                next.add(s.substring(0, k) + s.substring(k + 1));
            }
        }
        list.addAll(current = next);
    }
    System.out.println(list);
    // prints "[abcd, abc, abd, bcd, acd, ac, ad, ab, bc, bd, cd]"

По сути, это поиск в ширину в глубине души. Вы начинаете с набора current, изначально содержащего String master. Затем на каждой итерации i вы проходите через for (String s : current) и генерируете набор next, который вы делаете, удаляя все возможные символы из s.

Effective Java 2nd Edition: пункт 25. Предпочитайте списки массивам , но если вы настаиваете на сохранении в String[], вы можете просто сделать следующее в конце.

    String[] arr = list.toArray(new String[0]);

Смотри также

• Заполнить массив данными списка