Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
public StringBuilder decode(char [] str, int[] start){
StringBuilder res = new StringBuilder("");
int multi = 0;
for(int i=0; i<str.length; ++i){
char c = str[i];
int multiDigit = 0;
while(c <= '9' && c >= '0' && i<str.length){
int n = Character.getNumericValue(c);
int multi = (int)Math.pow(10, multiDigit++) * n + multi;
++i;
}
if(cn >= 'a' && cn <= 'Z'){
for(int cn=0; cn<multi; ++cn){
res.append(cn);
}
multi = 0;
}
if(c == '['){
StringBuilder sub = decode(str, i+1);
int bracketCount = 1;
while(bracketCount > 0){
++i;
c = str[i];
if(c == '['){
bracketCount++;
}else if(c == ']'){
bracketCount--;
}
}
for(int cn=0; cn<multi; ++cn){
res.append(cn);
}
multi = 0;
}
if(c == ']'){
return res;
}
}
return res;
}
// C++ code
// Assuming the final strings contain only chars from [a-z]
string Decode(const string& str)
{
stack<int> numStack;
stack<string> strStack;
string currStr;
int currNum = 0;
for (char ch : str)
{
if (ch >= '0' && ch <= '9')
{
currNum = 10 * currNum + (ch - '0');
}
else if (ch >= 'a' && ch <= 'z')
{
currStr += ch;
}
else if (ch == '[')
{
numStack.push(currNum);
currNum = 0;
strStack.push(currStr);
currStr.clear();
}
else if (ch == ']')
{
string tempStr = strStack.top();
strStack.pop();
int num = numStack.top();
numStack.pop();
for (int i = 0; i < num; ++i)
{
tempStr += currStr;
}
currStr = tempStr;
}
}
return currStr;
}
// ZoomBA
/*
Problem. We should think in terms of grammar rules.
Production Rules are :
G -> ( S )*
S -> <num> [ E+ ]
E -> S | <string>
There is no ambiguity, because Rule S starts with a number.
This is context free grammar.
I require a Stack/ But I would recurse
*/
def decode( encoded ){
cur_string = ''
inx = 0 ; len = size(encoded)
times = ''
while ( inx < len ){
switch ( encoded[inx] ){
case @$ @ '0123456789' :
// <num> rule
times += @$
case _'[' :
// inside recursive rule (S)
right_bra = inx
bra_count = 1
while ( bra_count != 0 ){
right_bra += 1
char = encoded[right_bra]
if ( char == _']' ){ bra_count -= 1 }
if ( char == _'[' ){ bra_count += 1 }
}
tmp = decode( encoded[ inx + 1 : right_bra -1 ] )
cur_string += ( tmp ** int( times ) )
times = ''
inx = right_bra
case @$:
// default case : we add up the string (<string>)
cur_string += @$
}
inx += 1
}
return cur_string
}
string = "3[abc2[ef]]"
println ( decode ( string ) )
public class StringDecoder {
/*
* USING RECURSION FOR THIS PROBLEM
* facebook-interview-questions Write code to decode strings. For example,
* String str = "3[a2[bd]g4[ef]h]", the output should be
* "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".
*/
Integer gblIndex = -1;
public static void main(String[] args) {
StringDecoder sd = new StringDecoder();
String encodedString = "3[a2[bd]g4[ef]h]";
String decodedString = sd.decodeString(encodedString, 0);
System.out.print(decodedString);
}
private String decodeString(String encodedString, int index) {
int multiplier = 1;
String str = "";
for (int i = index; i < encodedString.length(); i++) {
gblIndex++;
char indChar = encodedString.charAt(i);
if (isInt(indChar)) {
multiplier = Integer.parseInt(String.valueOf(indChar));
} else if (indChar == '[') {
String tempStr = decodeString(encodedString, i + 1);
while (multiplier >= 1) {
str = str + tempStr;
multiplier--;
}
multiplier++;
i = gblIndex;
} else if (indChar == ']') {
return str;
} else {
str = str + indChar;
}
}
return str;
}
private static boolean isInt(char indexOf) {
try {
Integer.parseInt(String.valueOf(indexOf));
} catch (NumberFormatException e) {
return false;
}
return true;
}
}
Recursive code... Hell yeah!
public class DecodeString {
static String decodeString(String s) {
if(s == null)
throw new IllegalArgumentException(s);
if(s.length() == 0)
return s;
StringBuffer sb = new StringBuffer();
for(int i=0; i < s.length(); i++) {
if(Character.isDigit(s.charAt(i)) && i+2 < s.length() && s.charAt(i+1) == '[') {
int times = Integer.parseInt(""+s.charAt(i));
i+=2;
String ss = s.substring(i);
String decoded = decodeString(ss);
while(times-- > 0)
sb.append(decoded);
i += decoded.length();
continue;
}
if(s.charAt(i) == ']') {
return sb.toString();
}
sb.append(s.charAt(i));
}
return sb.toString();
}
public static void main(String args[]) {
String str = "3[a2[bd]g4[ef]h]";
System.out.println(decodeString(str));
}
}
string = "3[a2[bd]g4[ef]h]"
def decoder(string, start=0):
decoded_string = ""
num = ""
i = start
while i < len(string):
x = string[i]
if x.isdigit():
num += x
i += 1
elif x.isalpha():
decoded_string += x
i += 1
elif x is "[":
temp, i = decoder(string, i+1)
decoded_string += temp*int(num)
num = ""
elif x is "]":
return decoded_string, i+1
return decoded_string
print decoder(string)
//Time Complexity: O(N) where N is the length of the string. Space Complexity: O(RN) where R is the number of repititions.
private static class Data{
int count;
String strVal;
private Data(int c){
count = c;
strVal ="";
}
}
public String decode(String str){
if(str == null || str.length() == 0){
throw new IllegalArgumentException();
}
Stack<Data> stk = new Stack<Data>();
int count = 0;
int strStart = -1;
for(int i = 0; i < str.length(); i++){
if((str.charAt(i) >= '0' && str.charAt(i) <= '9') || str.charAt(i) == ']'){
if(strStart != -1){
stk.peek().strVal = str.substring(strStart,i+1);
strStart = -1;
}
if(str.charAt(i) == ']'){
Data top = stk.pop();
String rep = applyRepition(top);
if(!stk.isEmpty()){
stk.peek().strVal += rep;
}else{
top.count = 1;
top.strVal = rep;
stk.push(top);
}
}else{
count *= 10;
count += ((int)(str.charAt(i) - '0'));
}
}
if (str.charAt(i) == '['){
stk.add(new Data());
stk.peek().count = count;
count = 0;
}
}
return applyReptition(stk.pop());
}
private String applyRepitition(Data d){
if(d.count == 1){
return d.strVal;
}
StringBuilder bldr = new StringBuilder(d.count * d.strVal.length());
int ct = d.count;
while(ct > 0){
bldr.append(d.strVal());
ct--;
}
return bldr.toString();
}
#include <string>
#include <iostream>
enum class CharacterType
{
Digit,
OpenBracket,
CloseBracket,
Text,
Terminate
};
static CharacterType characterType(const char ch)
{
switch(ch)
{
case 0:
return CharacterType::Terminate;
case '[':
return CharacterType::OpenBracket;
case ']':
return CharacterType::CloseBracket;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
return CharacterType::Digit;
default:
return CharacterType::Text;
}
}
static uint32_t parseNumber(const char *start, const char *end)
{
const char *digitPointer = end-1;
uint32_t result = 0;
uint32_t multiplier = 1;
while(digitPointer >= start)
{
char digit = *digitPointer--;
result += (digit - '0') * multiplier;
multiplier *= 10;
}
return result;
}
static const char *expand(uint32_t repeatCount, const char * const input, std::string &result)
{
char ch;
CharacterType type;
const char *pointer;
while(repeatCount > 0)
{
repeatCount--;
pointer = input;
for(;;)
{
ch = *pointer;
type = characterType(ch);
if(type == CharacterType::Terminate)
break;
if(type == CharacterType::Digit)
{
const char *lastDigitPointer = pointer+1;
while(characterType(*lastDigitPointer) == CharacterType::Digit)
lastDigitPointer++;
uint32_t childRepeatCount = parseNumber(pointer, lastDigitPointer);
pointer = lastDigitPointer;
ch = *pointer;
type = characterType(ch);
if(type == CharacterType::OpenBracket)
{
pointer = expand(childRepeatCount, pointer+1, result);
}
else if(type == CharacterType::Text)
{
while(childRepeatCount>0)
{
result.push_back(ch);
childRepeatCount--;
}
++pointer;
type = characterType(ch);
}
}
else if(type == CharacterType::Text)
{
result.push_back(ch);
++pointer;
}
else if(type == CharacterType::OpenBracket)
{
pointer = expand(1, pointer+1, result);
}
else if(type == CharacterType::CloseBracket)
{
++pointer;
break;
}
}
}
return pointer;
}
std::string decode(const std::string &input)
{
std::string result;
expand(1, input.c_str(), result);
return result;
}
int main(void)
{
auto result = decode("3[a2[bd]g4[ef]h]");
std::cout << result << std::endl;
return 0;
}
#include <string>
#include <iostream>
enum class CharacterType
{
Digit,
OpenBracket,
CloseBracket,
Text,
Terminate
};
static CharacterType characterType(const char ch)
{
switch(ch)
{
case 0:
return CharacterType::Terminate;
case '[':
return CharacterType::OpenBracket;
case ']':
return CharacterType::CloseBracket;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
return CharacterType::Digit;
default:
return CharacterType::Text;
}
}
static uint32_t parseNumber(const char *start, const char *end)
{
const char *digitPointer = end-1;
uint32_t result = 0;
uint32_t multiplier = 1;
while(digitPointer >= start)
{
char digit = *digitPointer--;
result += (digit - '0') * multiplier;
multiplier *= 10;
}
return result;
}
static const char *expand(uint32_t repeatCount, const char * const input, std::string &result)
{
char ch;
CharacterType type;
const char *pointer;
while(repeatCount > 0)
{
repeatCount--;
pointer = input;
for(;;)
{
ch = *pointer;
type = characterType(ch);
if(type == CharacterType::Terminate)
break;
if(type == CharacterType::Digit)
{
const char *lastDigitPointer = pointer+1;
while(characterType(*lastDigitPointer) == CharacterType::Digit)
lastDigitPointer++;
uint32_t childRepeatCount = parseNumber(pointer, lastDigitPointer);
pointer = lastDigitPointer;
ch = *pointer;
type = characterType(ch);
if(type == CharacterType::OpenBracket)
{
pointer = expand(childRepeatCount, pointer+1, result);
}
else if(type == CharacterType::Text)
{
while(childRepeatCount>0)
{
result.push_back(ch);
childRepeatCount--;
}
++pointer;
type = characterType(ch);
}
}
else if(type == CharacterType::Text)
{
result.push_back(ch);
++pointer;
}
else if(type == CharacterType::OpenBracket)
{
pointer = expand(1, pointer+1, result);
}
else if(type == CharacterType::CloseBracket)
{
++pointer;
break;
}
}
}
return pointer;
}
std::string decode(const std::string &input)
{
std::string result;
expand(1, input.c_str(), result);
return result;
}
int main(void)
{
auto result = decode("3[a2[bd]g4[ef]h]");
std::cout << result << std::endl;
return 0;
}
public static String decode(String str){
if(str==null||str.length()<1) return 0;
Stack<String> st=new Stack<>();
char[] strarray=str.toCharArray();
int num=1;
st.add("");
String temp="";
String sumstr="";
for(int i=0;i<strarray.length;i++){
if(Character.isLetter(strarray[i])){
temp=""+strarray[i];
while(i+1<strarray.length&&Character.isLetter(strarray[i+1])){
temp=temp+strarray[i+1];
i++;
}
substr+=temp;
}else if(Character.isDigit(strarray[i])){
num=strarray[i]-'0';
while(i+1<strarray.length&&Character.isDigit(strarray[i+1])){
num=num*10+strarray[i+1]-'0';
i++;
}
}else if(strarray[i]=='['){
st.add(substr);
st.add(String.valueOf(num));
substr="";
num=1;
}else if(strarray[i]==']'){
int getnum=Integer.parseInt(st.pop());
String t=st.pop();
for(int i=0;i<getnum;i++){
t=t+sumstr;
}
sumstr=t;
}
}
return sumstr;
}
function parseBrace (s) {
var modifier = ''
var i = 0
while (s.charAt(i).match(/[0-9]/)) {
modifier += s.charAt(i++)
}
var S = []
if (s.charAt(i) !== '[') {
throw new Error()
}
var j = i
S.push(s.charAt(j))
var argument = ''
while (S.length) {
j++
if (s.charAt(j) === '[') {
S.push(s.charAt(j))
} else if (s.charAt(j) === ']') {
S.pop()
}
if (S.length) {
argument += s.charAt(j)
}
}
return {
modifier_length: modifier.length,
modifier: parseInt(modifier, 10),
argument: argument
}
}
function tokenize (s) {
var tokens = []
var i = 0
while (i < s.length) {
if (s.charAt(i).match(/[0-9]/)) {
var token = parseBrace(s.slice(i))
i += token.modifier_length + 2 + token.argument.length
tokens.push(token)
} else {
tokens.push({argument: s.charAt(i++)})
}
}
return tokens
}
function parse (s) {
var tokens = tokenize (s)
var final = []
tokens.reverse()
while (tokens.length) {
var token = tokens.pop()
if (token.modifier_length) {
var moreTokens = tokenize(token.argument)
for (var j = 0; j < token.modifier; ++j) {
for (var k = moreTokens.length - 1; k > -1; --k) {
tokens.push(moreTokens[k])
}
}
} else {
final.push(token)
}
}
var S = ''
for (var i = 0; i < final.length; ++i) {
S += final[i].argument
}
return S
}
var s = '3[a2[bd]g4[ef]h]'
// s = '2[bd]g4[ef]h'
var solution = parse(s)
console.log(solution)
console.log("abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh")
$ node parse-braces.js
abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh
abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh
package strings;
import java.util.Stack;
public class DecodeString {
/**
* ITERATIVE METHOD
*/
public static String decode(String str) {
Stack<String> s = new Stack<>();
String ns = "";
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// string that will be repeated
if (Character.isLetter(c)) {
ns += String.valueOf(c);
}
// encountered number
if (!Character.isLetter(c) && !"[".equals(String.valueOf(c)) && !"]".equals(String.valueOf(c))) {
// stack is empty this is our first encounter so push number to stack
if (s.isEmpty()) {
s.push(String.valueOf(c));
} else {
// second encounter we push the ns we have constructed so far
// then the new number
// then clear the string to continue creating the string that will need to be repeated
s.push(ns);
s.push(String.valueOf(c));
ns = "";
}
}
if ("]".equals(String.valueOf(c)) && i < str.length() - 1) {
// we reached our repeat case the ']' so get the number of times we need to repeat
// repeat the string that has been constructed
// pop the other string we have pushed to the stack and concat it to the repeated string
int repeat = Integer.valueOf(s.pop());
ns = repeatCopy(ns, repeat);
ns = s.pop() + ns;
}
}
if (!s.isEmpty()) {
int repeat = Integer.valueOf(s.pop());
ns = repeatCopy(ns, repeat);
}
return ns;
}
/**
* RECURSIVE METHOD
*/
// "3[a2[bd]g4[ef]h]"
public static String decodeRec(String str, int repeat) {
String ns = "";
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// construct string that will be repeated
if (Character.isLetter(c)) {
ns += String.valueOf(c);
}
// encountered number rec call
if (!Character.isLetter(c) && !"[".equals(String.valueOf(c)) && !"]".equals(String.valueOf(c))) {
ns += decodeRec(str.substring(i + 1), Integer.valueOf(String.valueOf(c)));
// once the rec call returns set it to the end to either break
// out of the loop
// or to loop one last time for the first entry into our
// recursive stack
i = str.length() - 1;
c = str.charAt(i);
}
// closed bracket is our indicator to start repeating
if ("]".equals(String.valueOf(c))) {
ns = repeatCopy(ns, repeat);
// once we have repeatedly copied the string we build
// set repeat to 0 so we don't do it again when we reach the end
// of string
repeat = 0;
}
}
return ns;
}
public static String repeatCopy(String str, int num) {
if (num == 0) {
return str;
}
String temp = "";
for (int i = 0; i < num; i++) {
temp += str;
}
return temp;
}
}
import java.util.*;
public class DecodeStringQuestion
{
public static void main(String[] args)
{
String input = "3[a2[b3[X]d]g4[ef2[z]]h]";
System.out.println(decodeString(input));
}
public static String decodeString(String input){
char openBrace = '[';
char closeBrace = ']';
Stack<Integer> numStack = new Stack<Integer>();
Stack<String> stringStack = new Stack<String>();
int currentReplication = -1;
String currentString = "";
for(int i = 0; i < input.length(); i++){
if(input.charAt(i) == openBrace){
int newLimit = input.charAt(i - 1) -'0';
currentString = currentString.substring(0, currentString.length()-1);
if(currentReplication > -1){
numStack.push(currentReplication);
}
currentReplication = newLimit;
stringStack.push(currentString);
currentString = "";
}else if(input.charAt(i) == closeBrace){
System.out.println(Arrays.toString(stringStack.toArray()));
String startingString = stringStack.pop();
String finalString = "";
finalString += startingString;
// exited the current scope, pop up to next level
if(currentReplication == -1){
startingString += currentString;
currentString = startingString;
currentReplication = numStack.pop();
if(!stringStack.empty()){
finalString = stringStack.pop();
}
}
for(int j = 0; j < currentReplication; j++){
finalString += currentString;
}
currentReplication = -1;
currentString = "";
stringStack.push(finalString);
}else{
currentString += input.charAt(i);
}
}
return stringStack.pop();
}
}
// Java
public static class Decoder {
private static class SubPattern {
int start, end, repeat, numDigits;
}
// Find sub-patter that doesn't have other patterns inside e.g. 2[ab] not 3[2[sd]a]
public static SubPattern findSubPattern(String str) {
SubPattern sp = new SubPattern();
int i = 0;
while (i < str.length()) {
if (str.charAt(i) == '[') {
sp.start = i;
setNumDigits(str, i, sp);
}
if (str.charAt(i) == ']') {
sp.end = i;
return sp;
}
i++;
}
return null;
}
// determine number of times to repeat the pattern found
public static void setNumDigits(String str, int before, SubPattern subPattern) {
int i = before - 1, result = 0, digits = 0, digit = str.charAt(i) - '0';
while (i >= 0 && digit >= 0 && digit <= 9) {
result += (Math.pow(10, digits) * digit);
digits++;
i--;
if (i >= 0) {
digit = str.charAt(i) - '0';
}
}
subPattern.numDigits = digits;
subPattern.repeat = Math.max(1, result);
}
// repeate the pattern
public static String repeat(String fullStr, SubPattern subPattern) {
String str = fullStr.substring(subPattern.start + 1, subPattern.end);
int num = subPattern.repeat;
String result = "";
while (num > 0) {
result += str;
num--;
}
return result;
}
public static String decode(String src) {
String str = src;
SubPattern sp = findSubPattern(str);
// Repeat while we still have something to decode.
while (sp != null) {
str = str.substring(0, sp.start - sp.numDigits) + repeat(str, sp)
+ ((sp.end < str.length() - 1) ? str.substring(sp.end + 1) : "");
sp = findSubPattern(str);
}
return str;
}
}
c# implementation
static string DecodeString(string str)
{
string decodedString = "";
string numberChars = "";
Stack<KeyValuePair<string, int>> decoder = new Stack<KeyValuePair<string, int>>();
//We need to search the string and push items onto a stack to track them
for (int i = 0; i < str.Length; i++)
{
if (char.IsNumber(str[i]))
{
numberChars += str[i];
}
else if(str[i] == '[')
{
int multiplier = Convert.ToInt32(numberChars);
decoder.Push(new KeyValuePair<string, int>(decodedString, multiplier));
decodedString = "";
numberChars = "";
}
else if(str[i] == ']')
{
KeyValuePair<string, int> top = decoder.Pop();
string addToString = string.Concat(Enumerable.Repeat(decodedString, top.Value));
decodedString = top.Key + addToString;
}
else
{
decodedString += str[i];
}
}
return decodedString;
}
public class StringDecoder {
public static String decode(char[] arr, int x){
StringBuilder ret = new StringBuilder();
int multiple = 0;
for (int i=x; i<arr.length ; i++){
char c = arr[i];
if (c == '['){
String r = null;
for (int j=0; j<multiple; j++){
r = decode(arr, i+1);
ret.append(r);
}
for (int k=0; k< r.length() +1 ; k++){
i++;
}
multiple = 0;
} else if (c == ']'){
return ret.toString();
} else if (Character.isDigit(c)){
multiple *= 10;
multiple += Character.getNumericValue(c);
} else {
ret.append(c);
}
}
return ret.toString();
}
public static void main(String[] args){
System.out.println(StringDecoder.decode("3[a2[bd]g4[ef]h]".toCharArray(), 0));
}
}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
// 3[a2[bd]g4[ef]h] -> abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh
class Node{
int value;
Node rightChild;
Node leftChild;
public Node(int value){
this.value = value;
this.rightChild = null;
this.leftChild = null;
}
}
class Solution { /// 3 --> [ --> a
//3[a2[bd]g4[ef]h] -> [ -> a2[bd]g4[ef]h -> 3a2[bd]g4[ef]h -> a2[bd]g4[ef
public static String decode(String input){
int count=0;
boolean flag=false;
int index=0;
String aux="";
for(int i=0; i < input.length();i++){
// System.out.println(input.charAt(i));
if(input.charAt(i) == '['){
count++;
if(flag==false){
index=i;
}
flag=true;
}else if(input.charAt(i)==']'){
count--;
}
if(flag && count==0){
int mult =Integer.parseInt(""+input.charAt(index-1));
String before = input.substring(0,index-1);
String after = input.substring(i+1,input.length());
aux = input.substring(index+1,i);
String ss="";
//System.out.println(index);
for(int j=0;j<mult;j++){
ss+=aux;
}
//System.out.println(aux);
//a2[bd]g4[ef]h
aux = before+ss+after;
break;
}
}
return aux;
}
public static void main(String[] args) {
String input = "3[a2[bd]g4[ef]h]";
String input2 = "a2[bd]g4[ef]h";
String input3 = "a2[bd]3[cc]";
int indexOf = input.indexOf('[');
String s = input3;
while(indexOf!=-1){
s = decode(s);
System.out.println(s);
indexOf = s.indexOf('[');
}
// System.out.println(s);
//System.out.println(decode(input));
}
}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
// 3[a2[bd]g4[ef]h] -> abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh
class Node{
int value;
Node rightChild;
Node leftChild;
public Node(int value){
this.value = value;
this.rightChild = null;
this.leftChild = null;
}
}
class Solution { /// 3 --> [ --> a
//3[a2[bd]g4[ef]h] -> [ -> a2[bd]g4[ef]h -> 3a2[bd]g4[ef]h -> a2[bd]g4[ef
public static String decode(String input){
int count=0;
boolean flag=false;
int index=0;
String aux="";
for(int i=0; i < input.length();i++){
// System.out.println(input.charAt(i));
if(input.charAt(i) == '['){
count++;
if(flag==false){
index=i;
}
flag=true;
}else if(input.charAt(i)==']'){
count--;
}
if(flag && count==0){
int mult =Integer.parseInt(""+input.charAt(index-1));
String before = input.substring(0,index-1);
String after = input.substring(i+1,input.length());
aux = input.substring(index+1,i);
String ss="";
//System.out.println(index);
for(int j=0;j<mult;j++){
ss+=aux;
}
//System.out.println(aux);
//a2[bd]g4[ef]h
aux = before+ss+after;
break;
}
}
return aux;
}
public static void main(String[] args) {
String input = "3[a2[bd]g4[ef]h]";
String input2 = "a2[bd]g4[ef]h";
String input3 = "a2[bd]3[cc]";
int indexOf = input.indexOf('[');
String s = input3;
while(indexOf!=-1){
s = decode(s);
System.out.println(s);
indexOf = s.indexOf('[');
}
// System.out.println(s);
//System.out.println(decode(input));
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
Stack<Integer> opsStack = new Stack<>();
Stack<String> patStack = new Stack<>();
StringBuilder sb = new StringBuilder();
char[] letters = input.toCharArray();
for (char c : letters) {
if (((int) c) > 47 && (((int) c) < 57)) {
opsStack.push((int) (c - '0'));
} else if (c == '[') {
patStack.push("");
} else if (c == ']') {
String pat = patStack.pop();
StringBuilder pb = new StringBuilder("");
int op = opsStack.pop();
for (int i = 0; i < op; i++) {
pb.append(pat);
}
if (patStack.empty()) {
patStack.push(pb.toString());
} else {
patStack.push(patStack.pop() + pb.toString());
}
} else {
patStack.push(patStack.pop() + c);
}
}
System.out.println(patStack.peek());
}
}
public Pair<String, String> decode(String input){
if (TextUtils.isEmpty(input)) return "";
StringBuilder sb = new StringBuilder();
int num = 1;
StringBuilder accumulator = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
Character c = input.charAt(i));
if (c.isDigit()) {
for (int j = 0; j < num; j++) { // add chars found so far
sb.append(accumulator.toString());
accumulator.delete(0, accumulator.length());
}
num = Integer.valueOf(c);
continue;
} else if (c.isLetter()) {
accumulator.append(c);
continue;
} else if (c == '[') {
Pair<String, String> p = decode(input.substring(i+1, input.length())));
i += p.first().length();
accumulator.append(s);
} else if (c == ']') {
for (int j = 0; j < num; j++) {
sb.append(accumulator.toString());
}
return new Pair (input.substring(0, i), sb.toString());
}
}
sb.append(accumulator.toString());
return new Pair(input, sb.toString());
}
def decode_string(input_str):
segment = ''
t_count = ''
seg_open = False
characters = list(input_str)
while len(characters) > 0:
char = characters.pop(0)
if char.isdigit():
t_count += char
elif char is '[':
characters, part = decode_string(characters)
segment += int(t_count) * part
t_count = ''
elif char is ']':
break
elif char.isalpha():
segment += char
return characters, segment
def main():
in_str = '3[a2[bd]g4[aa]h]'
output = decode_string(in_str)
print output
in_str = '3[a2[bd]g10[q]h]'
output = decode_string(in_str)
print output
here is my take on the question, Its in O(n) . Basically I pop out characters from the initial list and then if I see a bracket opening I recursively try to resolve the inner parts of the bracket and returning the popped out character lists and the part of the inner brackets so it can concat those to the segment thats on the outer scope of the recursion.
import java.util.regex.Matcher;
import java.util.regex.Pattern;
private static String findRegex(String s, String regexPattern) {
Pattern pattern = Pattern.compile(regexPattern);
Matcher matcher = pattern.matcher(s);
if (matcher.find()) {
return matcher.group();
}
return null;
}
private static String stringDecoder(String s) {
String patternString = "([0-9]+\\[[a-z]+\\])";
do {
String group = findRegex(s, patternString);
int repetitions = Integer.parseInt(findRegex(group, "[0-9]+"));
String textToRepeat = findRegex(group, "[a-zA-Z]+");
String repeatedText = "";
while (repetitions-- > 0) repeatedText += textToRepeat;
s = s.replace(group, repeatedText);
} while (s.matches(".*"+patternString+".*"));
return s;
}
Solution:
1. keep pushing into stack<string> each character ( as string) until "]" is found.
2. When "]" is found , keep looking back into stack and keep appending words until "[" is found.
3. When "[" is found in step 2, keep looking back until digits are being seen ( the number could be 23 , 456 etc , hence keep looking back into stack". This no is "ctr"
4. Now build the comboString say bd and loop through ctr times while pushing into stack this comboString
public static String decode(String str){
Stack<String> stack = new Stack<String>();
for(int i=0;i<=str.length()-1;i++){
String s = str.substring(i,i+1);
if(!s.equals( "]") ){
stack.push(s);
}else{
String comboStr = "";
while(!stack.peek().equals("[")){
comboStr = stack.pop() + comboStr;
}
stack.pop(); // remove "["
int ctr= 0;
String ctrStr = "";
while(!stack.isEmpty() && stack.peek().charAt(0) >= '0' && stack.peek().charAt(0) <='9'){
ctrStr = stack.pop() + ctrStr;
}
ctr=Integer.parseInt(ctrStr);
//Integer.parseInt(stack.pop());
System.out.println("ctr="+ctr);
while(ctr>0){ // repeat the string
stack.push(comboStr);
ctr--;
}
System.out.println("comboStr="+comboStr);
}
}
str="";
for(String s : stack){ // stack navigates from bottom to top
str = str + s;
}
return str;
}
Interesting problem. It can be solved in O(n) time and O(n) space. The idea of the algorithm is to store the string built so far, and the replication factor every time "[" is encountered in a stack, and pop from the stack whenever a "]" is encountered.
For example, if input string is "2[c3[ab]]" then the following sequence is executed:
1. See first "[" and push ("", 2) onto stack
2. See "c" and do stringSoFar = "c"
3. See second "[" and push (stringSoFar, 3) = ("c", 3) onto stack. Reset stringSoFar = ""
4. See "a" and set stringSoFar = "a"
5. See "b" and set stringSoFar = "ab"
6. See first "]" and pop ("c", 3) from stack. Now set stringSoFar = "c" + "ab"x3 = "cababab"
7. See second "]" and pop ("", 2) from stack. Now set stringSoFar = "" + "cababab"x2 = "cabababcababab"
8. Reach end of input. Return stringSoFar.
Here is my code implementation in Java:
- Killedsteel January 19, 2017public class StringDecoder { public static void main(String[] args) { System.out.println(decode("3[a2[bd]g4[ef]h]".toCharArray())); } public static String decode(char[] input) { Stack<Pair> history = new Stack<>(); int multiplier = 1; int iterIdx = 0; StringBuilder localBuilder = new StringBuilder(); while(iterIdx < input.length) { StringBuilder numBuilder = null; if(isNumber(input[iterIdx])) { // read replication lengths numBuilder = new StringBuilder(); while (isNumber(input[iterIdx])) { numBuilder.append(input[iterIdx]); iterIdx += 1; } } if(numBuilder != null) { multiplier = Integer.valueOf(numBuilder.toString()); } if(input[iterIdx] == '[') { // trigger - store state on stack history.push(new Pair(multiplier, localBuilder.toString())); localBuilder = new StringBuilder(); } else if(input[iterIdx] == ']') { // trigger - pop stack and add to global builder // cash in on localBuilder Pair last = history.pop(); String toAppend = replicate(localBuilder.toString(), last.nextMultiplier); localBuilder = new StringBuilder(); localBuilder.append(last.builtSoFar) .append(toAppend); } else { localBuilder.append(input[iterIdx]); } iterIdx += 1; } return localBuilder.toString(); } private static String replicate(String template, Integer numReplicas) { StringBuilder sb = new StringBuilder(); for(int j=0; j<numReplicas; j++) { sb.append(template); } return sb.toString(); } private static boolean isNumber(char c) { switch(c) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': return true; default: return false; } } } class Pair { Integer nextMultiplier; String builtSoFar; Pair(Integer nextMultiplier, String builtSoFar) { this.nextMultiplier = nextMultiplier; this.builtSoFar = builtSoFar; } }