Автор оригинала: Pankaj Kumar.
В этом уроке мы узнаем, как найти перестановку строки в программе Java. Это сложный вопрос, и его задают в основном в интервью на Java.
Алгоритм перестановки строки в Java
Сначала мы возьмем первый символ из строки и переставим его с оставшимися символами.
Если
Первая и оставшиеся перестановки символов-это BC и CB.
Теперь мы можем вставить первый символ в доступные позиции в перестановках.
BC -> ABC, BAC, BCA
CB -> ACB, CAB, CBA
Мы можем написать рекурсивную функцию для возврата перестановок, а затем другую функцию для вставки первых символов, чтобы получить полный список перестановок.
Java – программа для печати перестановок строки
package com.journaldev.java.string; import java.util.HashSet; import java.util.Set; /** * Java Program to find all permutations of a String * @author Pankaj * */ public class StringFindAllPermutations { public static SetpermutationFinder(String str) { Set perm = new HashSet (); //Handling error scenarios if (str == null) { return null; } else if (str.length() == 0) { perm.add(""); return perm; } char initial = str.charAt(0); // first character String rem = str.substring(1); // Full string without first character Set words = permutationFinder(rem); for (String strNew : words) { for (int i = 0;i<=strNew.length();i++){ perm.add(charInsert(strNew, initial, i)); } } return perm; } public static String charInsert(String str, char c, int j) { String begin = str.substring(0, j); String end = str.substring(j); return begin + c + end; } public static void main(String[] args) { String s = "AAC"; String s1 = "ABC"; String s2 = "ABCD"; System.out.println("\nPermutations for " + s + " are: \n" + permutationFinder(s)); System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1)); System.out.println("\nPermutations for " + s2 + " are: \n" + permutationFinder(s2)); } }
Я использовал Set для хранения перестановок строк. Так что дубликаты удаляются автоматически.
Выход
Permutations for AAC are: [AAC, ACA, CAA] Permutations for ABC are: [ACB, ABC, BCA, CBA, CAB, BAC] Permutations for ABCD are: [DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADBC, ADCB, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]
Это все для поиска всех перестановок строки в Java.