Рубрики

Напечатайте все перестановки строки без повторения, используя Коллекции в 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