جایگزینی های یک رشته داده شده با استفاده از STL  


سطح دشواری متوسط
اغلب در آمازون سیب ByteDance ای بی فیس بوک گوگل مایکروسافت وحی
مجوز STL رشته

بیان مسأله  

در مسئله "Permutations of a მოცემه رشته با استفاده از STL" ، ما یک داده ایم رشته "s" با استفاده از توابع STL همه جایگزینی های رشته ورودی را چاپ کنید.

قالب ورودی  

اولین و تنها یک خط حاوی یک رشته "s" است.

فرمت خروجی  

همه جایگزینی های رشته داده شده را در جایی چاپ کنید که هر خط فقط شامل یک رشته باشد.

محدودیت ها  

  •  1 <= | ثانیه | <= 10
  • s [i] باید حروف کوچک انگلیسی باشد

مثال  

ABC
ABC
ACB
BCA
BAC
CAB
CBA

شرح: در اینجا کل جایگزینی های 3 * 2 * 1 وجود دارد. پس از انجام عملیات ، ABC ، ​​ACB ، BCA ، BAC ، CAB ، CBA را به عنوان پاسخ خود دریافت می کنیم.

الگوریتم جایگزینی یک رشته داده شده با استفاده از STL  

مجوز "ترتیب ترتیب" یا "ترتیب" نیز نامیده می شود ، ترتیب مجدد عناصر لیست مرتب شده S به صورت مکاتبه ای یک به یک با خود S است. یک رشته طول n دارای n است! جایگشت در اینجا ما از تابع next_permute () استفاده می کنیم که رشته داده را مرتب می کند و جایگزین بعدی را از نظر واژه نامه برمی گرداند.

La "چرخش ()" تابع عناصر یک بردار / رشته را می چرخاند به طوری که عنصر میانی عبور داده شده اول می شود. به عنوان مثال ، اگر ما برای "abc" rotate می گوییم که عنصر دوم آن وسط است ، رشته "bca" می شود. و اگر دوباره به عنوان عنصر دوم چرخش را با وسط بنامیم ، رشته "تاکسی" می شود.

  • رشته های s ورودی را از کاربر و رشته های خالی دیگری را از آن استفاده کنید.
  • هنگامی که اندازه str به 0 تبدیل می شود ، ans یک جایگزین دارد (طول "ans" n است).
  • همه کاراکترها را در ابتدای رشته "ans" یک به یک حرکت دهید.
  • اولین کاراکتر را از str حذف کرده و به “ans” اضافه کنید.
  • رشته را با یک کاراکتر به سمت چپ بچرخانید.
همچنین مشاهده کنید
الگوی کلمه

پیاده سازی  

++ C برنامه برای جایگزینی یک رشته داده شده با استفاده از STL

#include <bits/stdc++.h>
using namespace std;


void permute(string s, string ans)
{
  if(s.size()==0)
  {
    cout<<ans<<endl;
    return;
  }
  for(int i=0;i<s.size();i++)
  {
    permute(s.substr(1),ans+s[0]);
    rotate(s.begin(),s.begin()+1,s.end());
  }
}

int main()
{
  string s;
  cin>>s;
  permute(s,"");
  return 0;
}

برنامه جاوا برای جایگزینی های یک رشته داده شده با استفاده از STL

import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static String leftrotate(String str)
    {
            String ans = str.substring(1) + str.substring(0, 1);
            return ans;
    }
    public static void permute(String s, String ans)
    {
            if(s.length()==0)
            {
                    System.out.println(ans);
                    return;
            }
            for(int i=0;i<s.length();i++)
            {
                    permute(s.substring(1),ans+s.charAt(0));
                    s = leftrotate(s);
            }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        permute(s,"");
    }
}




cup
cup
cpu
upc
ucp
pcu
puc

تجزیه و تحلیل پیچیدگی برای جایگزینی یک رشته داده شده با استفاده از STL  

پیچیدگی زمان

بر!) جایی که n اندازه رشته داده شده است. در اینجا همه جایگزینی های رشته داده شده "s" را چاپ می کنیم.

پیچیدگی فضا

O (N) جایی که n اندازه رشته داده شده است. ما از این فضا برای ذخیره رشته ای استفاده می کنیم که نشان دهنده جایگزینی خاص قبل از چاپ آن است.