Problem Statement is present at
https://leetcode.com/problems/decode-string/
Idea:
Lets say string is 2[a]3[bc]
Take two stacks - First stack contains the number encountered and other the characters encountered.
When you hit closing bracket, then unwind char stack to create the string to be repeated and read from number stack the frequency of repetition,
Solution:
class Solution {
stack<int> numStack;
stack<int> charStack;
string retString;
private:
bool isInt(char x){
if ( ((x-'0')>=0) && ((x-'9') <=9)){
return true;
}
return false;
}
public:
string decodeString(string s) {
for (int i=0;i<s.size();i++){
char x = s.at(i);
if (isInt(x)){
int v = 0;
int tempL = 0;
while (isInt(s.at(i+tempL))){
v = (v *10) + (s.at(i+tempL) - '0');
tempL++;
}
//tempL--;
tempL--;
i = i+tempL;
numStack.push(v);
}else{
if (numStack.empty()){
retString = retString + x;
continue;
}
if (x != ']'){
charStack.push(x);
}else{
int repeatCount = numStack.top();
numStack.pop();
char stringChar = charStack.top();
string iString ;
while (stringChar != '['){
iString = stringChar + iString;
charStack.pop();
stringChar = charStack.top();
}
charStack.pop();
string tempString;
for (int count=0;count<repeatCount;count++)
tempString = tempString + iString;
if (numStack.empty()){
retString = retString + tempString;
}else{
for (int index=0;index<tempString.size();index++ )
charStack.push(tempString.at(index));
}
}
}
}
return retString;
}
};
https://leetcode.com/problems/decode-string/
Idea:
Lets say string is 2[a]3[bc]
Take two stacks - First stack contains the number encountered and other the characters encountered.
When you hit closing bracket, then unwind char stack to create the string to be repeated and read from number stack the frequency of repetition,
Solution:
class Solution {
stack<int> numStack;
stack<int> charStack;
string retString;
private:
bool isInt(char x){
if ( ((x-'0')>=0) && ((x-'9') <=9)){
return true;
}
return false;
}
public:
string decodeString(string s) {
for (int i=0;i<s.size();i++){
char x = s.at(i);
if (isInt(x)){
int v = 0;
int tempL = 0;
while (isInt(s.at(i+tempL))){
v = (v *10) + (s.at(i+tempL) - '0');
tempL++;
}
//tempL--;
tempL--;
i = i+tempL;
numStack.push(v);
}else{
if (numStack.empty()){
retString = retString + x;
continue;
}
if (x != ']'){
charStack.push(x);
}else{
int repeatCount = numStack.top();
numStack.pop();
char stringChar = charStack.top();
string iString ;
while (stringChar != '['){
iString = stringChar + iString;
charStack.pop();
stringChar = charStack.top();
}
charStack.pop();
string tempString;
for (int count=0;count<repeatCount;count++)
tempString = tempString + iString;
if (numStack.empty()){
retString = retString + tempString;
}else{
for (int index=0;index<tempString.size();index++ )
charStack.push(tempString.at(index));
}
}
}
}
return retString;
}
};
No comments:
Post a Comment