Google Interview Question
SDE-2sTeam: AdsWorld
Country: India
Interview Type: Phone Interview
Keep the already parsed characters in the vector, and print if all characters from string are read into the vector.
#include <iostream>
using namespace std;
#include <unordered_map>
#include<list>
#include <string>
#include <vector>
#include <cassert>
#include <sstream>
#include <cctype>
void print_comb(const string &s, int index, int max_index, vector<char> st) {
if (index == max_index) {
for(vector<char>::iterator it = st.begin(); it != st.end(); ++it) {
cout << *it;
}
cout <<"\n";
return;
}
st.push_back(s[index]);
print_comb(s, index+1, max_index, st);
st.pop_back(); // remove current
int count = 1;
// now add the number
if (!st.empty()) {
if (isdigit(st.back())) {
// get the digit and increase the count.
count += (int)(st.back() - '0');
st.pop_back();
}
}
char to_print = (char)(count + '0');
st.push_back(to_print);
print_comb(s, index+1, max_index, st);
}
void find_combinations(std::string s) {
if (!s.length()) {
return;
}
vector<char> st;
print_comb(s, 0, s.length(), st);
}
int main() {
// your code goes here
std:string str("ABCD");
find_combinations(str);
return 0;
}
public static List<string> abbreviations(string s)
{
if (string.IsNullOrEmpty(s) || s.Length == 0) { return null; }
if (s.Length == 1)
{
return new List<string>() { "1" };
}
List<string> ret = abbreviationsActual(s);
ret.Remove(s);
return ret;
}
private static List<string> abbreviationsActual(string s)
{
List<string> thislist = new List<string>() { s.Substring(0,1), "1" };
if (s.Length == 1)
{
return thislist;
}
List<string> abbrlist = abbreviationsActual(s.Substring(1));
List<string> result = new List<string>();
foreach (string a in thislist)
{
foreach (string b in abbrlist)
{
result.Add(a + b);
}
}
return removeconsecutivedigits(result);
}
private static List<string> removeconsecutivedigits(List<string> l)
{
List<string> res = new List<string>() ;
for (int index = 0; index<l.Count; index++)
{
string s = l[index];
string result = string.Empty;
for (int i = 0; i < s.Length; i++)
{
char schar = s[i];
char rchar = result == "" ? '0' : result[result.Length - 1];
if (result == string.Empty)
{
result = result + schar;
}
else if (Char.IsDigit(schar) && Char.IsDigit(rchar))
{
int sum = Int32.Parse(rchar.ToString()) + Int32.Parse(schar.ToString());
result = result.Substring(0,result.Length - 1) + sum.ToString();
} else
{
result = result + schar;
}
}
res.Add(result);
}
return res;
}
void PrintAbbreviations(string const &s, string const abbr = "", int idx = 0)
{
if (idx >= s.size()) {
if (!abbr.empty() &&
abbr != s)
{
cout << abbr << "\n";
}
return;
}
PrintAbbreviations(s, abbr + s[idx], idx + 1);
bool prev_digit = !abbr.empty() && isdigit(abbr.back()) ? true : false;
if (!prev_digit) {
for (int i = idx; i < s.size(); ++i) {
PrintAbbreviations(s, abbr + to_string(i - idx + 1), i + 1);
}
}
}
My solution in Java:
public ArrayList<String> abbreviation(String s) {
return rec(s);
}
private ArrayList<String> rec(String s) {
if (s.length() == 1) {
ArrayList<String> res = new ArrayList<>();
res.add("1");
res.add(s);
return res;
}
char curr = s.charAt(0);
ArrayList<String> prev = rec(s.substring(1));
ArrayList<String> result = new ArrayList<>();
for (String p : prev) {
char first = p.charAt(0);
if (first >= '0' && first <= '9') { // it's a number
if (first < '9') {
Integer newNr = Integer.valueOf(first + "") + 1;
result.add(newNr + p.substring(1));
}
result.add(curr + p);
} else {
result.add(curr + p);
result.add("1" + p);
}
}
return result;
}
public static void solve(String str, int count, int idx, String asf) {
if (idx == str.length()) {
if (count == 0) {
System.out.println(asf);
} else {
System.out.println(asf + count);
}
return;
}
char c = str.charAt(idx);
if (count == 0) {
solve(str, 0, idx + 1, asf + c);
} else {
solve(str, 0, idx + 1, asf + count + c);
}
solve(str, count + 1, idx + 1, asf);
}
public static void main(String args[]) throws Exception {
encryptString("abcd", "", 0);
}
private static void encryptString(String str, String result, int start) {
if (start >= str.length()) {
p(result);
return;
}
int lastDigit = -1;
if (result != null && result.length() > 0 && Character.isDigit(result.toCharArray()[result.length() - 1])) {
lastDigit = result.toCharArray()[result.length() - 1];
}
if (lastDigit != -1) {
char elem[] = result.toCharArray();
elem[elem.length - 1] = (char) ((int) elem[elem.length - 1] + 1);
encryptString(str, new String(elem), start + 1);
} else {
encryptString(str, result + 1, start + 1);
}
encryptString(str, result + str.toCharArray()[start], start + 1);
}
public static void p(String str) {
System.out.println(str);
}
edited: of course memoization would avoid repetition of work (different prefix same suffix) and speed up things
- Chris June 06, 2017