STL을 사용한 주어진 문자열의 순열

난이도 중급
자주 묻는 질문 아마존 Apple ByteDance 이베이 Facebook 구글 Microsoft 신탁
순열 STL 조회수 297

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"STL을 사용한 주어진 문자열의 순열"문제에서 우리는 "에스". STL 함수를 사용하여 입력 문자열의 모든 순열을 인쇄합니다.

입력 형식

문자열 "s"를 포함하는 첫 번째 및 유일한 행입니다.

출력 형식

주어진 문자열의 모든 순열을 인쇄합니다. 여기서 모든 줄은 하나의 문자열 만 포함합니다.

제약

  •  1 <= | s | <= 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 () 함수를 사용합니다.

또한 “rotate ()” 함수는 전달 된 중간 요소가 첫 번째가되도록 벡터 / 문자열의 요소를 회전합니다. 예를 들어 중간을 두 번째 요소로 사용하여 "abc"에 대해 rotate를 호출하면 문자열은 "bca"가됩니다. 두 번째 요소로 가운데를 사용하여 회전을 다시 호출하면 문자열이 "cab"이됩니다.

  • 사용자로부터 입력 문자열 s와 다른 빈 문자열 ans를 가져옵니다.
  • str의 크기가 0이되면 ans는 순열을가집니다 ( "ans"의 길이는 n 임).
  • 문자열 "ans"의 시작 부분에있는 모든 문자를 하나씩 이동합니다.
  • str에서 첫 번째 문자를 제거하고 "ans"에 추가합니다.
  • 문자열을 왼쪽으로 한 문자 씩 회전합니다.

실시

STL을 사용하여 주어진 문자열의 순열을위한 C ++ 프로그램

#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을 사용하여 주어진 문자열의 순열을위한 Java 프로그램

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 주어진 문자열의 크기입니다. 이 공간을 사용하여 인쇄하기 전에 특정 순열을 나타내는 문자열을 저장합니다.

균열 시스템 설계 인터뷰
Translate »