Decode String Leetcode Solution
Decode String Leetcode Problem :
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Decode String Leetcode Solution :
Constraints :
- The length of string is between 1 and 30.
- String consist of lowercase english letters, digits or square brackets[].
- S is guaranteed to be valid input.
- All the integers of the string are in the range between 1 and 300.
Example 1:
Input: s = “3[a2[c]]”
Output: “accaccacc”
Example 2:
Input: s = “2[abc]3[cd]ef”
Output: “abcabccdcdcdef
Explanation
- If we see digit, it means that we need to form number, so just do it: multiply already formed number by
10and add this digit. - If we see open bracket
[, it means, that we just right before finished to form our number: so we put it into our stack. Also we put in our stack empty string. - If we have close bracket
], it means that we just finished[...]block and what we have in our stack: on the top it is solution for what we have inside bracktes, before we have number of repetitions of this stringrepand finally, before we have string built previously: so we concatenatestr2andstr1 * rep. - Finally, if we have some other symbol, that is letter, we add it the the last element of our stack.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
string decodeString(const string& s, int& i) {
string res;
while (i < s.length() && s[i] != ']') {
if (!isdigit(s[i]))
res += s[i++];
else {
int n = 0;
while (i < s.length() && isdigit(s[i]))
n = n * 10 + s[i++] - '0';
i++; // '['
string t = decodeString(s, i);
i++; // ']'
while (n-- > 0)
res += t;
}
}
return res;
}
string decodeString(string s) {
int i = 0;
return decodeString(s, i);
}
};
class Solution {
public String decodeString(String s) {
Stack< Integer>numStack=new Stack<>();
Stack< StringBuilder>strBuild=new Stack<>();
StringBuilder str = new StringBuilder();
int num=0;
for(char c:s.toCharArray()){
if(c>='0' && c<='9'){
num=num*10 +c -'0';
}
else if(c=='['){
strBuild.push(str);
str=new StringBuilder();
numStack.push(num);
num=0;
}else if(c==']'){
StringBuilder temp=str;
str=strBuild.pop();
int count=numStack.pop();
while(count-->0){
str.append(temp);
}
}else{
str.append(c);
}
}
return str.toString();
}
}
class Solution:
def decodeString(self, s):
# In python, List can be used as stack(by using pop()) and queue(by using pop(0))
result = []
for curr_char in s:
if curr_char == "]":
# Step2-1 : Find the (1)subStr and remove "[" in the stack
sub_str = []
while result[-1] != "[":
sub_str.append(result.pop())
sub_str = "".join(sub_str[::-1])
# Step2-2 : Find the (2)k and remove k in the stack
result.pop()
k = []
while len(result) > 0 and result[-1] <= "9":
k.append(result.pop())
k = int("".join(k[::-1]))
# Step2-3 : Repeat sub_str k times after stack
result += k*sub_str
else:
# Step1 : Put the char into the stack, except "]"
result.append(curr_char)
return "".join(result)
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment