시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
인코딩 된 문자열이 주어진다고 가정합니다. ㅏ 현 어떤 패턴으로 인코딩 된 경우 문자열을 디코딩해야합니다.
<문자열 발생 횟수> [문자열]
차례
예
입력
3 [b] 2 [bc]
산출
bbccaca
설명
여기로 "비" 3 회 발생하고 "ca" 2 번 발생합니다.
입력
2 [b2 [d]]
산출
bddbdd
설명
여기에서는 두 부분으로 먼저 작동합니다. "디" 2 번 반복하면 2 [bdd]가되고 두 번 반복하면 bddbdd가됩니다.
디코딩 문자열 알고리즘
- 임시 및 출력을 빈 문자열로 설정하면 나중에 일시적으로 문자열을 저장하는 데 사용할 것입니다.
- 0부터 시작하여 문자열 길이보다 작습니다.
str [i]가 숫자와 같은지 확인하고 정수 스택으로 푸시합니다. - 그렇지 않으면 str [i]가 ']'를 제외한 모든 문자와 같으면 문자 스택으로 푸시합니다.
- ']'가 발견되면 정수 스택에서 숫자를 팝하고 문자 스택의 모든 문자를 팝하고 '['가 발견되고 '['가 팝될 때까지 임시 문자열에 저장합니다.
- 정수 스택에서 숫자가 나올 때까지 출력 할 temp 값을 저장하고 추가합니다.
- 출력 문자열에서 모든 문자를 문자 스택으로 푸시하고 출력을 빈 문자열로 설정합니다.
- 캐릭터의 모든 캐릭터가 나올 때까지이 과정을 반복합니다. 스택 정수 스택의 정수가 popped ()됩니다.
- 문자 스택에서 모든 문자를 꺼내 출력에 저장합니다.
- 반환 출력
디코딩 문자열에 대한 설명
어떤 패턴으로 디코딩 된 문자열이 주어졌고,이를 인코딩하고 디코딩 된 문자열을 확인하는 적절한 문자열을 반환해야합니다.이를 위해 두 개의 다른 스택을 사용할 것입니다. 하나에는 정수를 저장하고 다른 스택에는 문자를 저장합니다.
3 [b2 [ca]]라는 문자열이 주어 졌다고 가정합니다. 이것은 "caca"를 의미하는 ac를 2 번 출력해야 함을 의미하고 이제 b와 연결되므로 내부에서 "bcaca"가되고이 문자열은 3 번 발생합니다. 그래서 그것은 bcacabcacabcaca가 될 것입니다.
예를 들어 보자
디코딩 문자열의 예
입력 : 3 [b2 [ca]]
i = 0;
str [i] = 3 정수 스택으로 푸시합니다.
i = 1;
str [i] = '['문자 스택으로 푸시됩니다.
i = 2;
str [i] = b, 문자 스택으로 푸시됩니다.
i = 3;
str [i] = '2'정수 스택으로 푸시합니다.
i = 4;
str [i] = '[', 문자 스택으로 푸시됩니다.
i = 5;
str [i] = 'c'문자 스택으로 푸시됩니다.
i = 6;
str [i] = 'a'문자 스택으로 푸시됩니다.
i = 7;
str [i] = ']'알고리즘에 따라이 ']'를 찾으면 이제 2 인 정수 스택에서 정수를 꺼내야하며 문자를 하나씩 꺼내어 임시 문자열에 저장해야합니다. '['이 문자를 발견하고 마침내이 문자를 팝할 때까지 문자 스택.
이제 temp는 "ca"가됩니다.
그 임시 문자열을 정수 스택에서 뽑은 숫자와 noOfInteger = 2로 곱하여 출력에 저장합니다.
따라서 Decode String의 출력은 입력 후 "caca"가됩니다. 문자 스택으로 다시 푸시해야합니다.
i = 8;
str [i] =“]”, 다시 이것을 찾았습니다. 이제 3 인 정수 스택에서 정수를 꺼내야합니다. 문자를 하나씩 꺼내어 찾을 때까지 문자 스택에서 임시 문자열에 저장해야합니다. '['이 캐릭터와 마침내이 캐릭터를 팝니다.
이제 temp는 "bcaca"가됩니다.
그 임시 문자열을 정수 스택에서 뽑은 숫자와 noOfInteger = 3로 곱하여 출력에 저장합니다.
따라서 출력은 "bcacabcacabcaca"가됩니다.
그 후 문자열의 길이에 도달하면 출력이 반환됩니다.
출력은“bcacabcacabcaca”입니다.
디코딩 문자열 구현
C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
string getDecodeString(string str)
{
stack<int> pushInt ;
stack<char> charStack ;
string temp = "";
string output = "";
for (int i = 0; i < str.length(); i++)
{
int noOfInteger = 0;
if (isdigit(str[i]))
{
while (isdigit(str[i]))
{
noOfInteger = noOfInteger * 10 + str[i] - '0';
i++;
}
i--;
pushInt.push(noOfInteger);
}
else if (str[i] == ']')
{
temp = "";
noOfInteger = 0;
if (!pushInt.empty())
{
noOfInteger = pushInt.top();
pushInt.pop();
}
while (!charStack.empty() && charStack.top()!='[' )
{
temp = charStack.top() + temp;
charStack.pop();
}
if (!charStack.empty() && charStack.top() == '[')
{
charStack.pop();
}
for (int j = 0; j < noOfInteger; j++)
{
output = output + temp;
}
for (int j = 0; j < output.length(); j++)
{
charStack.push(output[j]);
}
output = "";
}
else if (str[i] == '[')
{
if (isdigit(str[i-1]))
{
charStack.push(str[i]);
}
else
{
charStack.push(str[i]);
pushInt.push(1);
}
}
else
{
charStack.push(str[i]);
}
}
while (!charStack.empty())
{
output = charStack.top() + output;
charStack.pop();
}
return output;
}
int main()
{
string str = "3[b2[ca]]";
cout<<getDecodeString(str);
return 0;
}
bcacabcacabcaca
자바 프로그램
import java.util.Stack;
class stringDecoding
{
static String getDecodeString(String str)
{
Stack<Integer> pushInt = new Stack<>();
Stack<Character> charStack = new Stack<>();
String temp = "";
String output = "";
for (int i = 0; i < str.length(); i++)
{
int noOfInteger = 0;
if (Character.isDigit(str.charAt(i)))
{
while (Character.isDigit(str.charAt(i)))
{
noOfInteger = noOfInteger * 10 + str.charAt(i) - '0';
i++;
}
i--;
pushInt.push(noOfInteger);
}
else if (str.charAt(i) == ']')
{
temp = "";
noOfInteger = 0;
if (!pushInt.isEmpty())
{
noOfInteger = pushInt.peek();
pushInt.pop();
}
while (!charStack.isEmpty() && charStack.peek()!='[' )
{
temp = charStack.peek() + temp;
charStack.pop();
}
if (!charStack.empty() && charStack.peek() == '[')
{
charStack.pop();
}
for (int j = 0; j < noOfInteger; j++)
{
output = output + temp;
}
for (int j = 0; j < output.length(); j++)
{
charStack.push(output.charAt(j));
}
output = "";
}
else if (str.charAt(i) == '[')
{
if (Character.isDigit(str.charAt(i-1)))
{
charStack.push(str.charAt(i));
}
else
{
charStack.push(str.charAt(i));
pushInt.push(1);
}
}
else
{
charStack.push(str.charAt(i));
}
}
while (!charStack.isEmpty())
{
output = charStack.peek() + output;
charStack.pop();
}
return output;
}
public static void main(String args[])
{
String str = "3[b2[ca]]";
System.out.println(getDecodeString(str));
}
}
bcacabcacabcaca
위 코드 그림
복잡성 분석
시간 복잡성
여기서 시간 복잡도는 입력 문자열에 따라 달라지기 때문에 고정되지 않습니다. 매 단계를 반복하고 문자열을 연결할 때마다
공간 복잡성
O (N) 여기서 n은 문자열의 길이입니다. 구현을 위해 스택을 사용하고 스택의 가능한 최대 크기는 n입니다.
