#Day67 из #100days_of_coding

Вчера был мой 67-й день кодинга. я решил один вопрос

Проблема: перестановки заданной строки

Дана строка S. Задача состоит в том, чтобы вывести все уникальные перестановки заданной строки в лексикографически отсортированном порядке.

Пример 1:

Input: ABC
Output:
ABC ACB BAC BCA CAB CBA
Explanation:
Given string ABC has permutations in 6 
forms as ABC, ACB, BAC, BCA, CAB and CBA .

Пример 2:

Input: ABSG
Output:
ABGS ABSG AGBS AGSB ASBG ASGB BAGS 
BASG BGAS BGSA BSAG BSGA GABS GASB 
GBAS GBSA GSAB GSBA SABG SAGB SBAG 
SBGA SGAB SGBA
Explanation:
Given string ABSG has 24 permutations.

Ваша задача.
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию find_permutaion(), которая принимает строку S в качестве входного параметра и возвращает вектор строки в лексикографическом порядке.

Ожидаемая временная сложность:O(n! * n)

Ожидаемая сложность пространства:O(n)

Решение (в Java):

Основной подход заключается в использовании рекурсии и возврата.

class Solution {

    List<String> hs= new ArrayList<>();
    public List<String> find_permutation(String S) {
     
        permutation(0, S);
        Collections.sort(hs);
            
        return hs;
    }
    public void permutation(int index, String s){
        if(index==s.length()-1)
    {
        if(!hs.contains(s))
    hs.add(s);
    return;
        }  
        for(int i=index; i<s.length(); i++){
            s=swap(s, i, index);
            permutation(index+1,s );
            s=swap(s, i, index);
            
        }
    }
    public String swap(String s, int a, int b){
        char ch[]= s.toCharArray();
        char p=ch[a];
        ch[a]= ch[b];
        ch[b]= p;
        return String.valueOf(ch);
    }
}