Напечатайте все перестановки строки без повторения, используя Коллекции в Java

Учитывая строку str , задача состоит в том, чтобы напечатать все перестановки str . Перестановка — это расположение всего или части набора объектов с учетом порядка расположения. Перестановка не должна иметь повторяющихся строк в выводе.

Примеры:

Input: str = “aa”
Output:
aa
Note that “aa” will be printed only once
as duplicates are not allowed.
Input: str = “ab”
Output:
ab
ba

Подход: напишите рекурсивную функцию, которая удаляет один за другим символ из исходной строки и генерирует новую строку, добавляя эти удаленные символы. Базовое условие будет, когда все символы были использованы. В этом случае вставьте сгенерированную строку (перестановку исходной строки) в набор , чтобы избежать дублирования.

Ниже приведена реализация вышеуказанного подхода:

// Java реализация подхода

import java.util.*;

public class GFG {

static Set<String> hash_Set = new HashSet<>();

// Рекурсивная функция для генерации

// перестановки строки

static void Permutation(String str, String ans)

{

// Если строка пуста

if (str.length() == 0) {

// Добавить сгенерированную перестановку к

// установить, чтобы избежать дубликатов

hash_Set.add(ans);

return;

}

for (int i = 0; i < str.length(); i++) {

// i-й символ строки

char ch = str.charAt(i);

// Остальная часть строки после исключения

// i-й символ

String ros = str.substring(0, i)

+ str.substring(i + 1);

// Рекурсивный вызов

Permutation(ros, ans + ch);

}

// Код драйвера

public static void main(String[] args)

{

String s = "ab";

// Генерируем перестановки

Permutation(s, "");

// Распечатать сгенерированные перестановки

hash_Set.forEach((n) -> System.out.println(n));

}

Выход:

ab
ba

Рекомендуемые посты:

Напечатайте все перестановки строки без повторения, используя Коллекции в Java

0.00 (0%) 0 votes