Construct a string from an encoded sequence
A string that may contain multiple consecutive instances of the same value is encoded to only store that value and its count. Given such an encoded sequence, decode it.
A string inside the parenthesis will be repeated exactly as many times as the number preceding it. For example,
Input: str = 2(a)1(b)c4(de)f
Output: aabcdedededef
Input: str = 2(a2(b)c)
Output: abbcabbc
Input: str = a1(bc)4(c2(d)e)f10(h)
Output: abccddecddecddecddefhhhhhhhhhh
Output: aabcdedededef
Input: str = 2(a2(b)c)
Output: abbcabbc
Input: str = a1(bc)4(c2(d)e)f10(h)
Output: abccddecddecddecddefhhhhhhhhhh
You may presume that the number is non-negative and is exactly followed by a string within the parenthesis. Additionally, the input text has matching parenthesis and is free of whitespace.
1. Using Recursion
We can use recursion to solve this problem. The idea is to traverse the string, starting from the last processed index in the caller function. If we encounter a starting bracket '(', recursively decode the substring starting with '(' and ending with the matching ')'. After each recursive call, the decoded substring is appended to the result as many times as the number preceding '('. We follow the process recursively until the end of the string is reached.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <iostream> #include <string> using namespace std; // Utility function for constructing a string from string `str` repeated `n` times string repeat(string const &str, int n) { string s; s.reserve(str.size() * n); while (n--) { s.append(str); } return s; } // Utility function to extract the number from a string that starts at the i'th index // Note that `i` is passed by reference int extractCount(string const &str, int &i) { int n = 0; while (i < str.length() && isdigit(str[i])) { n = n * 10 + (str[i++] - '0'); } return n; } // Recursive function to construct a string from the encoded sequence // Note that `i` is passed by reference string decode(string const &str, int &i) { int n = 0; string result; // do until the end of the string is reached or the closing bracket is encountered while (i < str.length() && str[i] != ')') { // if the current digit is a number, extract the full number if (isdigit(str[i])) { n = extractCount(str, i); } // if we encounter a starting bracket else if (str[i] == '(') { // recursively decode the substring string ss = decode(str, ++i); // append the decoded substring to the result `n` times result.append(repeat(ss, n)); // move to the next character (i currently points to the closing bracket) i++; } else { result.push_back(str[i++]); } } return result; } // Main function to construct a string from the encoded sequence string decode(string const &str) { int i = 0; return decode(str, i); } int main() { string str = "a1(bc)4(c2(d)e)f10(h)"; cout << decode(str); return 0; } |
Output:
abccddecddecddecddefhhhhhhhhhh
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
import java.util.concurrent.atomic.AtomicInteger; class Main { // Utility function to extract the number from a string that starts at the i'th index public static int extractCount(String str, AtomicInteger i) { int n = 0; while (i.get() < str.length() && Character.isDigit(str.charAt(i.get()))) { n = n * 10 + (str.charAt(i.getAndIncrement()) - '0'); } return n; } // Recursive function to construct a string from the encoded sequence public static String decode(String str, AtomicInteger i) { int n = 0; StringBuilder result = new StringBuilder(); // do until the end of the string is reached or the closing bracket is encountered while (i.get() < str.length() && str.charAt(i.get()) != ')') { // if the current digit is a number, extract the full number if (Character.isDigit(str.charAt(i.get()))) { n = extractCount(str, i); } // if we encounter a starting bracket else if (str.charAt(i.get()) == '(') { // skip starting bracket i.incrementAndGet(); // recursively decode the substring String ss = decode(str, i); // append the decoded substring to the result `n` times result.append(ss.repeat(n)); // move to the next character (i currently points to the closing bracket) i.incrementAndGet(); } else { result.append(str.charAt(i.getAndIncrement())); } } return result.toString(); } // Main function to construct a string from the encoded sequence public static String decode(String str) { AtomicInteger i = new AtomicInteger(0); return decode(str, i); } public static void main(String[] args) { String str = "a1(bc)4(c2(d)e)f10(h)"; System.out.println(decode(str)); } } |
Output:
abccddecddecddecddefhhhhhhhhhh
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# Utility function to extract the number from a string that starts at the i'th index def extractCount(s, i): n = 0 while i < len(s) and s[i].isdigit(): n = n * 10 + (ord(s[i]) - ord('0')) i = i + 1 return n, i # Recursive function to construct a string from the encoded sequence def decode(s, i=0): n = 0 result = '' # do until the end of the string is reached or the closing bracket is encountered while i < len(s) and s[i] != ')': # if the current digit is a number, extract the full number if s[i].isdigit(): n, i = extractCount(s, i) # if we encounter a starting bracket elif s[i] == '(': # skip starting bracket i = i + 1 # recursively decode the substring ss, i = decode(s, i) # append the decoded substring to the result `n` times result += ss * n # move to the next character (i currently points to the closing bracket) i = i + 1 else: result += s[i] i = i + 1 return result, i if __name__ == '__main__': s = 'a1(bc)4(c2(d)e)f10(h)' print(decode(s)[0]) |
Output:
abccddecddecddecddefhhhhhhhhhh
The time complexity of the above solution is O(n) and requires O(n) extra space for the call stack, where n is the length of the string.
2. Using Iteration
We can convert the above recursive procedure into an iterative one using an explicit stack. Following is a simple stack-based iterative algorithm to construct a string from an encoded sequence:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <stack> #include <cctype> using namespace std; // Utility function for constructing a string from string `str` repeated `n` times string repeat(string const &str, int n) { string s; s.reserve(str.size() * n); while (n--) { s.append(str); } return s; } // Utility function to extract the number from a string that starts at the i'th index int extractCount(string str, int i) { int n = 0; while (isdigit(str[i])) { n = 10 * n + (str[i] - '0'); i++; } return n; } // Function to construct a string from the encoded sequence string decode(string str) { // take two stacks, one for storing the result so far and one for storing the count stack<string> stringStack; stack<int> numberStack; string result = ""; // loop through all characters of the string for (int i = 0; i < str.size(); i++) { // if the current digit is a number if (isdigit(str[i])) { // extract the full number and push it to the number stack int n = extractCount(str, i); numberStack.push(n); // move `i` to the next non-digit character i += to_string(n).size() - 1; } // if we encounter a starting bracket else if (str[i] == '(') { // push the result to the string stack and reset the result stringStack.push(result); result = ""; } // if we encounter a closing bracket else if (str[i] == ')') { // pop top items from the number and the string stack, // and reinitialize the result result = stringStack.top() + repeat(result, numberStack.top()); stringStack.pop(); numberStack.pop(); } else { result.push_back(str[i]); } } return result; } int main() { string str = "a1(bc)4(c2(d)e)f10(h)"; cout << decode(str) << endl; return 0; } |
Output:
abccddecddecddecddefhhhhhhhhhh
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.*; class Main { // Utility function to extract the number from a string that starts at the i'th index public static int extractCount(String str, int i) { int n = 0; while (Character.isDigit(str.charAt(i))) { n = 10 * n + (str.charAt(i) - '0'); i++; } return n; } // Function to construct a string from the encoded sequence public static String decode(String str) { // take two stacks, one for storing the result so far and one for storing the count Stack<Integer> numberStack = new Stack<>(); Stack<String> stringStack = new Stack<>(); String result = ""; // loop through all characters of the string for (int i = 0; i < str.length(); i++) { // if the current digit is a number if (Character.isDigit(str.charAt(i))) { // extract the full number and push it to the number stack int n = extractCount(str, i); numberStack.push(n); // move `i` to the next non-digit character i += String.valueOf(n).length() - 1; } // if we encounter a starting bracket else if (str.charAt(i) == '(') { stringStack.push(result); result = ""; } // if we encounter a closing bracket else if (str.charAt(i) == ')') { // pop top items from the number and the string stack, // and reinitialize the result result = stringStack.pop() + result.repeat(numberStack.pop()); } else { result += str.charAt(i); } } return result; } public static void main(String[] args) { String str = "a1(bc)4(c2(d)e)f10(h)"; System.out.println(decode(str)); } } |
Output:
abccddecddecddecddefhhhhhhhhhh
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
from collections import deque # Utility function to extract the number from a string that starts at the i'th index def extractCount(s, i): n = 0 while s[i].isdigit(): n = 10 * n + (ord(s[i]) - ord('0')) i = i + 1 return n # Function to construct a string from the encoded sequence def decode(s): # take two stacks, one for storing the result so far and one for storing the count numberStack = deque() stringStack = deque() result = '' # loop through all characters of the string i = 0 while i < len(s): # if the current digit is a number if s[i].isdigit(): # extract the full number and push it to the number stack n = extractCount(s, i) numberStack.append(n) # move `i` to the next non-digit character i += len(str(n)) - 1 # if we encounter a starting bracket elif s[i] == '(': # push the result to the string stack and reset the result stringStack.append(result) result = '' # if we encounter a closing bracket elif s[i] == ')': # pop top items from the number and the string stack, # and reinitialize the result result = stringStack[-1] + result * numberStack.pop() stringStack.pop() else: result += s[i] i += 1 return result if __name__ == '__main__': s = 'a1(bc)4(c2(d)e)f10(h)' print(decode(s)) |
Output:
abccddecddecddecddefhhhhhhhhhh
The time complexity of the above solution is O(n) and requires O(n) extra space for the stack data structure, where n is the length of the string.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)