Google Interview Question
Software EngineersCountry: United States
//Using regular expression.
//O(n), where n is the string length.
//It may take up to O(2^m) time and space to compile the regular expression, where m is the size of regex.
public static String reformat(String input) {
String regex = "^(.*)(\\{)(.*?)(\\})(.*)$";
Matcher matcher = Pattern.compile(regex).matcher(input);
String result = "";
if (matcher.find()) {
String[] rep = matcher.group(3).split(",");
for (int i = 0; i < rep.length; i++)
rep[i] = matcher.group(1) + rep[i] + matcher.group(5);
return matcher.group(2) + String.join(", ", rep) + matcher.group(4);
}
return input;
}
//Using regular expression.
//O(n), where n is the string length.
//It may take up to O(2^m) time and space to compile the regular expression, where m is the size of regex.
public static String reformat(String input) {
String regex = "^(.*)(\\{)(.*?)(\\})(.*)$";
Matcher matcher = Pattern.compile(regex).matcher(input);
String result = "";
if (matcher.find()) {
String[] rep = matcher.group(3).split(",");
for (int i = 0; i < rep.length; i++)
rep[i] = matcher.group(1) + rep[i] + matcher.group(5);
return matcher.group(2) + String.join(", ", rep) + matcher.group(4);
}
return input;
}
using recursion after creating a list of Nodes, for the example: "a{d,b,c}e", list of nodes:
Node(a,Node(dbc,Node(e)))
import java.util.LinkedList;
import java.util.List;
public class BraceExpansion {
public static final class Node {
private String value;
private Node next;
public Node(String value) {
this.value = value;
}
}
public List<String> expansion(String input) {
int n = input.length();
Node head = null;
Node previous = null;
for (int i = 0; i < n; ) {
char c = input.charAt(i);
Node newNode;
if (c == '{') {
int j = input.indexOf('}', i);
String s = input.substring(i + 1, j).replaceAll(",", "");
newNode = new Node(s);
i = j + 1;
} else {
newNode = new Node(c + "");
i++;
}
if (head == null) {
head = newNode;
previous = newNode;
} else {
previous.next = newNode;
previous = newNode;
}
}
List<String> result = new LinkedList<>();
dfs(head, new StringBuilder(), result);
return result;
}
private void dfs(Node head, StringBuilder sb, List<String> result) {
if (head == null) {
result.add(sb.toString());
} else {
for (char c: head.value.toCharArray()) {
dfs(head.next, sb.append(c), result);
}
}
if (sb.length() > 0) {
sb.setLength(sb.length() - 1);
}
}
public static void main(String[] args) {
BraceExpansion braceExpansion = new BraceExpansion();
List<String> expansion = braceExpansion.expansion("a{d,c,b}{e,f,g}");
System.out.println(expansion);
}
}
import java.util.LinkedList;
import java.util.List;
public class BraceExpansion {
public static final class Node {
private String value;
private Node next;
public Node(String value) {
this.value = value;
}
}
public List<String> expansion(String input) {
int n = input.length();
Node head = null;
Node previous = null;
for (int i = 0; i < n; ) {
char c = input.charAt(i);
Node newNode;
if (c == '{') {
int j = input.indexOf('}', i);
String s = input.substring(i + 1, j).replaceAll(",", "");
newNode = new Node(s);
i = j + 1;
} else {
newNode = new Node(c + "");
i++;
}
if (head == null) {
head = newNode;
previous = newNode;
} else {
previous.next = newNode;
previous = newNode;
}
}
List<String> result = new LinkedList<>();
dfs(head, new StringBuilder(), result);
return result;
}
private void dfs(Node head, StringBuilder sb, List<String> result) {
if (head == null) {
result.add(sb.toString());
} else {
for (char c: head.value.toCharArray()) {
dfs(head.next, sb.append(c), result);
}
}
if (sb.length() > 0) {
sb.setLength(sb.length() - 1);
}
}
public static void main(String[] args) {
BraceExpansion braceExpansion = new BraceExpansion();
List<String> expansion = braceExpansion.expansion("a{d,c,b}{e,f,g}");
System.out.println(expansion);
}
}
void ExpandString(std::string str1)
{
map<std::string, std::string> mapStrExpan;
int nLength = str1.length();
bool openBrace = false, closeBrace = false;
string strTemp = "";
for (int i = 0; i <nLength ; i++ )
{
strTemp = str1[i];
if (str1[i] == '{')
{
mapStrExpan[strTemp] ;
openBrace = true;
}
else if (str1[i] == '}')
{
mapStrExpan[strTemp];
openBrace = false;
closeBrace = true;
}
else
{
if(openBrace)
mapStrExpan["{"] += strTemp;
else if (closeBrace)
mapStrExpan["last"] += strTemp;
else
mapStrExpan["first"] += strTemp;
}
}
map<std::string, std::string>::iterator itMap;
map<std::string, std::string>::iterator itMapLast;
std::string expanString = "";
std::string strLast = "";
//seperating first last strings from the middle and printing in combination.
if ((itMapLast = mapStrExpan.find("first")) != mapStrExpan.end())
{
expanString += itMapLast->second;
}
if ((itMapLast = mapStrExpan.find("last")) != mapStrExpan.end())
{
strLast += itMapLast->second;
}
if ((itMapLast = mapStrExpan.find("{")) != mapStrExpan.end())
{
int nLeng = itMapLast->second.length();
std::string middlestr = itMapLast->second;
printf("Combination of Strings \r\n");
std::string strFinal;
for (int i = 0; i < nLeng; i++)
{
if (middlestr[i] != ',')
{
strFinal = expanString + middlestr[i] + strLast;
printf("%s\r\n", strFinal.c_str());
}
}
}
}
int main()
{
std::string str1 = "ahj{d,c,b,m,o,p,q}etu";
ExpandString(str1);
getchar();
}
package T12;
import java.util.ArrayList;
public class T12 {
private static final String input = "a{d,c,b}e";
public static void main(String[] args) {
boolean first = false, second = false;
ArrayList<String> firstS = new ArrayList<>();
ArrayList<String> secondS = new ArrayList<>();
ArrayList<String> thirdS = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char getChar = input.charAt(i);
switch (getChar) {
case '{':
first = true;
break;
case '}':
second = true;
break;
case ',':
break;
default:
if ((first == false) && (second == false)) {
firstS.add(String.valueOf(getChar));
} else if ((first == true) && (second == false)) {
secondS.add(String.valueOf(getChar));
} else if ((first == true) && (second == true)) {
thirdS.add(String.valueOf(getChar));
}
break;
}
}
String beforeS = new String();
String afterS = new String();
for (String temp : firstS) {
beforeS += temp;
}
for (String temp : thirdS) {
afterS += temp;
}
ArrayList<String> result = new ArrayList<>();
for (int k = 0; k < secondS.size(); k++) {
String temp = new String();
String mid = secondS.get(k);
temp = beforeS + mid + afterS;
result.add(temp);
}
System.out.println(result);
}
}
The problem looked like very easy, but it was actually not so trivial recursion. Rewrite input as fork join model. Code: ideone[dot]com/pW7gAr
- shakil0302 April 23, 2019