Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
C++, implementation, O(log n)
int numberAlphabetCombination(int n, map<int, int>& cache) {
map<int, int>::iterator it;
int count;
if (n <= 0) return 1;
it = cache.find(n);
if (it != cache.end()) {
return it->second;
}
count = numberAlphabetCombination(n / 10, cache);
if ((n % 100) >= 10 && (n % 100) <= 26) {
count += numberAlphabetCombination(n / 100, cache);
}
cache.insert(make_pair(n, count));
return count;
}
int solve(int n) {
map<int, int> cache;
return numberAlphabetCombination(n, cache);
}
public class StringDecoder {
public static void main(final String[] args) {
final Map<String, String> codes = new HashMap<>();
codes.put("0", "+");
codes.put("1", "A");
codes.put("2", "B");
codes.put("3", "C");
codes.put("4", "D");
codes.put("5", "E");
codes.put("6", "F");
codes.put("7", "G");
codes.put("8", "H");
codes.put("9", "I");
codes.put("10", "J");
codes.put("11", "K");
codes.put("12", "L");
codes.put("13", "M");
codes.put("14", "N");
codes.put("15", "O");
codes.put("16", "P");
codes.put("17", "Q");
codes.put("18", "R");
codes.put("19", "S");
codes.put("20", "T");
codes.put("21", "U");
codes.put("22", "V");
codes.put("23", "W");
codes.put("24", "X");
codes.put("25", "Y");
codes.put("26", "Z");
System.out.println(decode("1123", codes));
}
private static List<StringBuilder> decode(final String string, final Map<String, String> codes) {
List<StringBuilder> result = new ArrayList<StringBuilder>();
final Map<StringBuilder, Integer> indexMap = new HashMap<>();
char currentChar, nextChar = 0;
for (int i = 0; i < string.length(); i++) {
currentChar = string.charAt(i);
if (i < string.length() - 1) {
nextChar = string.charAt(i + 1);
} else {
nextChar = 0;
}
if (currentChar == '1' || (currentChar == '2' && nextChar >= '0' && nextChar <= '6')) {
final String code1 = codes.get("" + currentChar);
final String code2 = codes.get("" + currentChar + nextChar);
result = addToResult(code1, code2, i, result, indexMap);
} else {
final String code = codes.get("" + currentChar);
result = addToResult(code, result, i, indexMap);
}
}
return result;
}
private static List<StringBuilder> addToResult(final String code1, final String code2, final int index,
final List<StringBuilder> result, final Map<StringBuilder, Integer> indexMap) {
final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
if (result.isEmpty()) {
final StringBuilder decodeString1 = new StringBuilder(code1);
final StringBuilder decodeString2 = new StringBuilder(code2);
resultStringbuilder.add(decodeString1);
resultStringbuilder.add(decodeString2);
indexMap.put(decodeString1, index);
indexMap.put(decodeString2, index + 1);
} else {
for (final StringBuilder decodedString : result) {
final int indexForDeocdedString = indexMap.get(decodedString);
if (indexForDeocdedString < index) {
final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code1);
resultStringbuilder.add(newDecodedString);
indexMap.put(newDecodedString, index);
final StringBuilder newDecodedString2 = new StringBuilder(decodedString).append(code2);
resultStringbuilder.add(newDecodedString2);
indexMap.put(newDecodedString2, index + 1);
} else {
resultStringbuilder.add(decodedString);
}
}
}
return resultStringbuilder;
}
private static List<StringBuilder> addToResult(final String code, final List<StringBuilder> result,
final int index, final Map<StringBuilder, Integer> indexMap) {
final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
if (result.isEmpty()) {
resultStringbuilder.add(new StringBuilder(code));
} else {
for (final StringBuilder decodedString : result) {
final int indexForDeocdedString = indexMap.get(decodedString);
if (indexForDeocdedString < index) {
final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code);
resultStringbuilder.add(newDecodedString);
indexMap.put(newDecodedString, index);
} else {
resultStringbuilder.add(decodedString);
}
}
}
return resultStringbuilder;
}
}
public class StringDecoder {
public static void main(final String[] args) {
final Map<String, String> codes = new HashMap<>();
codes.put("0", "+");
codes.put("1", "A");
codes.put("2", "B");
codes.put("3", "C");
codes.put("4", "D");
codes.put("5", "E");
codes.put("6", "F");
codes.put("7", "G");
codes.put("8", "H");
codes.put("9", "I");
codes.put("10", "J");
codes.put("11", "K");
codes.put("12", "L");
codes.put("13", "M");
codes.put("14", "N");
codes.put("15", "O");
codes.put("16", "P");
codes.put("17", "Q");
codes.put("18", "R");
codes.put("19", "S");
codes.put("20", "T");
codes.put("21", "U");
codes.put("22", "V");
codes.put("23", "W");
codes.put("24", "X");
codes.put("25", "Y");
codes.put("26", "Z");
System.out.println(decode("1123", codes));
}
private static List<StringBuilder> decode(final String string, final Map<String, String> codes) {
List<StringBuilder> result = new ArrayList<StringBuilder>();
final Map<StringBuilder, Integer> indexMap = new HashMap<>();
char currentChar, nextChar = 0;
for (int i = 0; i < string.length(); i++) {
currentChar = string.charAt(i);
if (i < string.length() - 1) {
nextChar = string.charAt(i + 1);
} else {
nextChar = 0;
}
if (currentChar == '1' || (currentChar == '2' && nextChar >= '0' && nextChar <= '6')) {
final String code1 = codes.get("" + currentChar);
final String code2 = codes.get("" + currentChar + nextChar);
result = addToResult(code1, code2, i, result, indexMap);
} else {
final String code = codes.get("" + currentChar);
result = addToResult(code, result, i, indexMap);
}
}
return result;
}
private static List<StringBuilder> addToResult(final String code1, final String code2, final int index,
final List<StringBuilder> result, final Map<StringBuilder, Integer> indexMap) {
final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
if (result.isEmpty()) {
final StringBuilder decodeString1 = new StringBuilder(code1);
final StringBuilder decodeString2 = new StringBuilder(code2);
resultStringbuilder.add(decodeString1);
resultStringbuilder.add(decodeString2);
indexMap.put(decodeString1, index);
indexMap.put(decodeString2, index + 1);
} else {
for (final StringBuilder decodedString : result) {
final int indexForDeocdedString = indexMap.get(decodedString);
if (indexForDeocdedString < index) {
final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code1);
resultStringbuilder.add(newDecodedString);
indexMap.put(newDecodedString, index);
final StringBuilder newDecodedString2 = new StringBuilder(decodedString).append(code2);
resultStringbuilder.add(newDecodedString2);
indexMap.put(newDecodedString2, index + 1);
} else {
resultStringbuilder.add(decodedString);
}
}
}
return resultStringbuilder;
}
private static List<StringBuilder> addToResult(final String code, final List<StringBuilder> result,
final int index, final Map<StringBuilder, Integer> indexMap) {
final List<StringBuilder> resultStringbuilder = new ArrayList<StringBuilder>();
if (result.isEmpty()) {
resultStringbuilder.add(new StringBuilder(code));
} else {
for (final StringBuilder decodedString : result) {
final int indexForDeocdedString = indexMap.get(decodedString);
if (indexForDeocdedString < index) {
final StringBuilder newDecodedString = new StringBuilder(decodedString).append(code);
resultStringbuilder.add(newDecodedString);
indexMap.put(newDecodedString, index);
} else {
resultStringbuilder.add(decodedString);
}
}
}
return resultStringbuilder;
}
}
This is a Dinamic Propramming question, if we just want to know the number of combinations:
public int GetNumCombinations(string s)
{
int[] dp = new int[s.Length];
dp[0] = IsValid(ToInt(s[0])) ? 1 : 0;
for (int i=1; i < s.Length; i++)
{
dp[i] = dp[i - 1];
if (IsValid(ToInt(s[i-1]), ToInt(s[i])))
{
int j = i > 2 ? i - 2 : 0;
dp[i] += dp[j];
}
}
return dp[s.Length -1];
}
private bool IsValid(int first)
{
return IsValid(first, null);
}
private bool IsValid(int first, int? second)
{
if (first == 0)
return false;
if (second.HasValue)
{
if (first > 2)
return false;
if (first == 2 && second.Value > 6)
return false;
}
return true;
}
private int ToInt(char c)
{
return (int)(c - '0');
}
public void numPermutations(int num, String result) {
if(num < 1) {
System.out.println(result);
return;
}
if (num < 10) {
System.out.println(codes().get(num) + result);
return;
}
int lastTwo = num % 100;
if (lastTwo <= 26) {
numPermutations(num / 10, codes().get(lastTwo % 10) + result);
numPermutations(num / 100, codes().get(lastTwo) + result);
} else {
numPermutations(num / 100, result);
}
}
public static Map<Integer, String> codes() {
final Map<Integer, String> codes = new HashMap<>();
codes.put(0, "+");
codes.put(1, "A");
codes.put(2, "B");
codes.put(3, "C");
codes.put(4, "D");
codes.put(5, "E");
codes.put(6, "F");
codes.put(7, "G");
codes.put(8, "H");
codes.put(9, "I");
codes.put(10, "J");
codes.put(11, "K");
codes.put(12, "L");
codes.put(13, "M");
codes.put(14, "N");
codes.put(15, "O");
codes.put(16, "P");
codes.put(17, "Q");
codes.put(18, "R");
codes.put(19, "S");
codes.put(20, "T");
codes.put(21, "U");
codes.put(22, "V");
codes.put(23, "W");
codes.put(24, "X");
codes.put(25, "Y");
codes.put(26, "Z");
return codes;
}
If we need to return all the strings we can use recursion and a string builder but is really inefficient, This is based on a DP solution you just check the current and last chars according to that update the lists; I used list of integers instead of string builders is more easy to do the operations/comparations.
public List<string> GetCombinations(string s)
{
var result = new List<string>();
if (string.IsNullOrEmpty(s))
return result;
int i = 0;
var list = new List<List<int>>();
// Add the first valid element to the first list
while (!IsValid(s[i]))
i++;
if (i < s.Length)
{
var newList = new List<int>();
newList.Add(ToInt(s[i]));
list.Add(newList);
i++;
}
while (i < s.Length)
{
// If is valid update the existing list.
if (IsValid(s[i]))
{
int n1 = ToInt(s[i]);
foreach (var item in list)
item.Add(n1);
}
// If the current and previus numbers form a valid letter add new lists.
if (IsValid(s[i - 1], s[i]))
{
int n1 = ToInt(s[i - 1]);
int n2 = ToInt(s[i]);
int n = (n1 * 10) + n2;
var list2 = new List<List<int>>();
foreach (var item in list)
{
int m = -1;
// Special case when n2 == 0, the 0 is not in the item list and there is only one eleent
if (n2 == 0 && item.Count > 0 && item[item.Count - 1] == n1)
m = item.Count - 1;
else if (item.Count > 1 && item[item.Count - 2] == n1 && (n2 == 0 || item[item.Count - 1] == n2))
m = item.Count - 2;
if (m == -1)
continue;
var newList = new List<int>();
for (int j = 0; j < m; j++)
newList.Add(item[j]);
newList.Add(n);
list2.Add(newList);
}
list.AddRange(list2);
}
i++;
}
// Parse int values to char
foreach (var item in list)
result.Add(ToString(item));
return result;
}
private bool IsValid(char c)
{
return IsValid(c, null);
}
private bool IsValid(char c1, char? c2)
{
int n1 = ToInt(c1);
if (n1 == 0 || n1 > 9)
return false;
if (c2.HasValue)
{
int n2 = ToInt(c2.Value);
if (n1 > 2)
return false;
if (n1 == 2 && n2 > 26)
return false;
}
return true;
}
private int ToInt(char c)
{
return (int)(c - '0');
}
private char ToChar(int n)
{
return (char)((int)'A' + n - 1);
}
private string ToString(List<int> list)
{
var sb = new StringBuilder();
foreach (var item in list)
sb.Append(ToChar(item));
return sb.ToString();
}
public void Test(object sender, EventArgs e)
{
var s = "1123";
//var s = "134524";
//var s = "1203";
var list = GetCombinations(s);
foreach (var item in list)
Console.WriteLine(item);
}
var input = [1,1,2,3];
function equals(a, b){
if(a.length != b.length) return false;
for(let i = 0; i < a.length; i++){
if(a[i] != b[i]) return false;
}
return true;
}
function found(r,m){
for(let arr of r){
if(equals(arr,m)) return true;
}
return false;
}
function find(input, results = []){
if(!found(results, input))results.push(input);
for(let i = 0; i < input.length -1; i++){
if(input[i+1]>=10 && input[i] != 0) continue;
let m = input[i]*10 +input[i+1];
if(m <27){
let tmp = input.slice();
tmp.splice(i,2,m);
find(tmp,results,i);
}
}
return results.length;
}
var r = [];
find(input,r);
for(let x of r){
console.log(x);
}
console.log('length: ',r.length);
int numCombination(int num) {
Map<Integer, Integer> memo = new HashMap<>();
return numCombinationHelper(num, memo);
}
int numCombinationHelper(int num, Map<Integer, Integer> memo) {
if (num < 10) {
return 1;
}
if (memo.get(num) == null) {
if (num % 100 < 27) {
memo.put(num, numCombinationHelper(num/10, memo) + numCombinationHelper(num/100, memo));
} else {
memo.put(num, numCombinationHelper(num/10, memo));
}
}
return memo.get(num);
}
size_t getDigNum(int inp) {
vector<short> digs;
while(inp > 0) {
digs.push_back(inp % 10);
inp /= 10;
}
for(size_t i = 0; i < digs.size() / 2; ++i) {
swap(digs[i], digs[digs.size() - i - 1]);
}
size_t prev = 1;
size_t cur = 1;
for (size_t i = 1; i < digs.size(); ++i) {
if (digs[i-1] < 2 || (digs[i-1] == 2 && digs[i] < 7)) {
size_t tmp = cur;
cur += prev;
prev = tmp;
} else {
prev = cur;
}
}
return cur;
}
A simple recursive solution
private static final Map<String, String> map = new HashMap<>();
public static void main(String[] args) {
map.put("1", "A");
map.put("2", "B");
map.put("3", "C");
map.put("11", "J");
map.put("23", "W");
combinations("1123", "");
}
private static void combinations(String str, String result) {
for (int i = 1; i <= str.length(); i++) {
String prefix = str.substring(0, i);
if (map.containsKey(prefix)) {
if (i == str.length()) {
System.out.println(result + map.get(prefix));
}
combinations(str.substring(i, str.length()), result + map.get(prefix) + "");
}
}
}
public class Combinations {
public static void main(String[] args) {
String number = "0123";
System.out.println("\nNumber: "+findCombinations(number,0,number.length()));
}
private static int findCombinations(String number,int index, int maxIndex) {
int sum =0;
if(index>=maxIndex){
System.out.println(number);
return 1;
}else{
if(index+1<=maxIndex){
String remainingString ="";
if(index+1<maxIndex){
remainingString = number.substring(index+1);
}
sum = sum + findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+1)) + remainingString,
index+1, number.length());
}
if(index+2<=maxIndex){
String remainingString ="";
if(index+2<maxIndex){
remainingString = number.substring(index+2);
}
sum =sum +findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+2))+ remainingString, index+1, number.length()-1);
}
}
return sum;
}
private static String convertNumberToString(String charAt) {
int intVal = Integer.valueOf(charAt);
if(intVal==0){
return "+";
}
char a = (char)(intVal + 64);
return a+"";
}
}
public class Combinations {
public static void main(String[] args) {
String number = "0123";
System.out.println("\nNumber: "+findCombinations(number,0,number.length()));
}
private static int findCombinations(String number,int index, int maxIndex) {
int sum =0;
if(index>=maxIndex){
System.out.println(number);
return 1;
}else{
if(index+1<=maxIndex){
String remainingString ="";
if(index+1<maxIndex){
remainingString = number.substring(index+1);
}
sum = sum + findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+1)) + remainingString,
index+1, number.length());
}
if(index+2<=maxIndex){
String remainingString ="";
if(index+2<maxIndex){
remainingString = number.substring(index+2);
}
sum =sum +findCombinations(number.substring(0, index)+convertNumberToString(number.substring(index, index+2))+ remainingString, index+1, number.length()-1);
}
}
return sum;
}
private static String convertNumberToString(String charAt) {
int intVal = Integer.valueOf(charAt);
if(intVal==0){
return "+";
}
char a = (char)(intVal + 64);
return a+"";
}
}
public class NumberCombinations {
public static void main(String[] args) {
String number = "1123";
int count = 0;
int nextCount =0;
for(int i=0;i<=number.length()-2;i++) {
nextCount =0;
String Substring = number.substring(i, i+2);
if(Integer.parseInt(Substring)<27){
if(Substring.charAt(0) !='0'){
count++;
}
}
for(int j=number.lastIndexOf(Substring)+2;j<=number.length()-2;j++){
String Substring2 = number.substring(j, j+2);
if(Integer.parseInt(Substring2)<27){
if(Substring2.charAt(0) !='0'){
nextCount++;
}
}
}
if(nextCount>0){
count++;
}
}
System.out.println(count+1);
}
}
public class NumberCombinations {
public static void main(String[] args) {
String number = "1123";
int count = 0;
int nextCount =0;
for(int i=0;i<=number.length()-2;i++) {
nextCount =0;
String Substring = number.substring(i, i+2);
if(Integer.parseInt(Substring)<27){
if(Substring.charAt(0) !='0'){
count++;
}
}
for(int j=number.lastIndexOf(Substring)+2;j<=number.length()-2;j++){
String Substring2 = number.substring(j, j+2);
if(Integer.parseInt(Substring2)<27){
if(Substring2.charAt(0) !='0'){
nextCount++;
}
}
}
if(nextCount>0){
count++;
}
}
System.out.println(count+1);
}
}
# Pure string version.
def ci(x):
return chr(int(x) + ord('A') - 1)
def cc(x):
return chr(ord(x) + ord('A') - 1)
myChr = [ x for x in "1123"]
# --- print all the onesies
for i in myChr: print ci(i),
print
myTwos = [ int(myChr[i])*10 + int(myChr[i+1]) for i in range(0,len(myChr),2)]
for x in myTwos:
if x < 27:
print ci(x),
print
for j in range(len(myChr)-1):
i = j
while i < len(myChr):
k = 0;
while k <= (j-1):
print ci(myChr[k]),
k = k + 1
print ci(10*int(myChr[j])+int(myChr[j+1])),
if j == i: i = i + 1
k = j+2;
while k < len(myChr):
print ci(myChr[k]),
k = k + 1;
i = i + 1
print
i = i + 1
#include<iostream>
#include<deque>
#include<vector>
#include<list>
using namespace std;
void displayq (deque<vector<int> > &d) {
for(int i=0; i<d.size(); i++) {
vector<int> v = d[i];
for(int j=0; j<v.size(); j++) {
cout << v[j] << " ";
}
for(int j=0; j<v.size(); j++) {
cout << char('A' + v[j] -1) ;
}
cout << endl;
}
}
int main() {
int arr[] = {1,1,2,3};
int n = sizeof(arr)/sizeof(arr[0]);
int i=0;
deque<vector<int> > dqlstint;
vector <int> v ;
for(int i=0; i<n; i++)
v.push_back(arr[i]);
dqlstint.push_back(v);
while(i<dqlstint.size() ) {
vector<int> front = dqlstint[i];
int temp=0;
for(int j=0; j<front.size()-1; j++) {
vector<int> front2 = front;
if( (temp = ((front[j]*10)+front[j+1])) <= 26 && front[j] < 10 && front[j+1] < 10 ) {
front2[j] = temp;
front2.erase(front2.begin() + j +1);
int k=0;
while(k<dqlstint.size() ) {
if(dqlstint[k] == front2)
break;
k++;
}
if(k == dqlstint.size() )
dqlstint.push_back(front2);
}
}
i++;
}
displayq(dqlstint);
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int PrintValidCombinations(string s, int i){
if(i == s.length()-1){
return 1;
}else if (i == s.length()-2){
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number>26){
return 1;
}else{
return 2;
}
}
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number > 26){
return 1+PrintValidCombinations(s,i+2);
}else{
return PrintValidCombinations(s,i+1)+PrintValidCombinations(s,i+2);;
}
}
int main(){
std::string s;
cin>>s;
std::cout<<PrintValidCombinations(s,0)<<endl;
#include<iostream>
#include<string>
using namespace std;
int PrintValidCombinations(string s, int i){
if(i == s.length()-1){
return 1;
}else if (i == s.length()-2){
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number>26){
return 1;
}else{
return 2;
}
}
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number > 26){
return 1+PrintValidCombinations(s,i+2);
}else{
return PrintValidCombinations(s,i+1)+PrintValidCombinations(s,i+2);;
}
}
int main(){
std::string s;
cin>>s;
std::cout<<PrintValidCombinations(s,0)<<endl;
#include<iostream>
#include<string>
using namespace std;
int PrintValidCombinations(string s, int i){
if(i == s.length()-1){
return 1;
}else if (i == s.length()-2){
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number>26){
return 1;
}else{
return 2;
}
}
int number = (s[i]-'0')*10 + (s[i+1]-'0');
if(number > 26){
return 1+PrintValidCombinations(s,i+2);
}else{
return PrintValidCombinations(s,i+1)+PrintValidCombinations(s,i+2);;
}
}
int main(){
std::string s;
cin>>s;
std::cout<<PrintValidCombinations(s,0)<<endl;
static int ways(String s) {
if (s.length() == 1) {
return 1;
}
int i = 0;
int k = 1;
int j = 1;
while (i < s.length()-1) {
int temp = j;
if (is2Decodable(s, i)) {
j += k;
}
k = temp;
i++;
}
return j;
}
static boolean is2Decodable(String s, int i) {
if (i > s.length() - 2) {
return false;
}
return s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '6');
}
Non-recursive, O(n) by time, O(1) by space:
static int ways(String s) {
if (s.length() == 1) {
return 1;
}
int i = 0;
int k = 1;
int j = 1;
while (i < s.length()-1) {
int temp = j;
if (is2Decodable(s, i)) {
j += k;
}
k = temp;
i++;
}
return j;
}
static boolean is2Decodable(String s, int i) {
if (i > s.length() - 2) {
return false;
}
return s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '6');
}
static HashMap<Integer, Character> map;
static {
map = new HashMap<Integer,Character>();
map.put(1, 'A');
map.put(2, 'B');
map.put(3, 'C');
map.put(4, 'D');
map.put(5, 'E');
map.put(6, 'F');
map.put(7, 'G');
map.put(8, 'H');
map.put(9, 'I');
map.put(10, 'J');
map.put(11, 'K');
map.put(12, 'L');
map.put(13, 'M');
map.put(14, 'N');
map.put(15, 'O');
map.put(16, 'P');
map.put(17, 'Q');
map.put(18, 'R');
map.put(19, 'S');
map.put(20, 'T');
map.put(21, 'U');
map.put(22, 'V');
map.put(23, 'W');
map.put(24, 'X');
map.put(25, 'Y');
map.put(26, 'Z');
}
public static Set<String> getCombinations(String input){
return getCombinations("", input);
}
public static Set<String> getCombinations(String prefix, String suffix ){
Set<String> combinations = new HashSet<String>();
if(suffix.length() == 0){
combinations.add(prefix);
return combinations;
}
if(suffix.length() == 1){
combinations.add(prefix + map.get(Integer.valueOf(suffix.substring(0,1))));
return combinations;
}
combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,1))), suffix.substring(1)));
if(suffix.length() > 1 && suffix.charAt(0) == '1'){
combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));
}
if(suffix.length() > 1 && suffix.charAt(0) == '2' && (Integer.valueOf(suffix.substring(0,2)) <= 26)){
combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));
}
return combinations;
}
public static void main(String ... args){
Set<String> combinations = getCombinations("1123");
for(String s : combinations){
System.out.println(s);
}
}
static HashMap<Integer, Character> map;
static {
map = new HashMap<Integer,Character>();
map.put(1, 'A');
map.put(2, 'B');
map.put(3, 'C');
map.put(4, 'D');
map.put(5, 'E');
map.put(6, 'F');
map.put(7, 'G');
map.put(8, 'H');
map.put(9, 'I');
map.put(10, 'J');
map.put(11, 'K');
map.put(12, 'L');
map.put(13, 'M');
map.put(14, 'N');
map.put(15, 'O');
map.put(16, 'P');
map.put(17, 'Q');
map.put(18, 'R');
map.put(19, 'S');
map.put(20, 'T');
map.put(21, 'U');
map.put(22, 'V');
map.put(23, 'W');
map.put(24, 'X');
map.put(25, 'Y');
map.put(26, 'Z');
}
public static Set<String> getCombinations(String input){
return getCombinations("", input);
}
public static Set<String> getCombinations(String prefix, String suffix ){
Set<String> combinations = new HashSet<String>();
if(suffix.length() == 0){
combinations.add(prefix);
return combinations;
}
if(suffix.length() == 1){
combinations.add(prefix + map.get(Integer.valueOf(suffix.substring(0,1))));
return combinations;
}
combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,1))), suffix.substring(1)));
if(suffix.length() > 1 && suffix.charAt(0) == '1'){
combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));
}
if(suffix.length() > 1 && suffix.charAt(0) == '2' && (Integer.valueOf(suffix.substring(0,2)) <= 26)){
combinations.addAll(getCombinations(prefix + map.get(Integer.valueOf(suffix.substring(0,2))), suffix.substring(2)));
}
return combinations;
}
public static void main(String ... args){
Set<String> combinations = getCombinations("1123");
for(String s : combinations){
System.out.println(s);
}
}
public class NumberCombination {
private HashMap<Integer, String> codes;
public NumberCombination() {
codes = new HashMap<>();
codes.put(0, "+");
codes.put(1, "A");
codes.put(2, "B");
codes.put(3, "C");
codes.put(4, "D");
codes.put(5, "E");
codes.put(6, "F");
codes.put(7, "G");
codes.put(8, "H");
codes.put(9, "I");
codes.put(10, "J");
codes.put(11, "K");
codes.put(12, "L");
codes.put(13, "M");
codes.put(14, "N");
codes.put(15, "O");
codes.put(16, "P");
codes.put(17, "Q");
codes.put(18, "R");
codes.put(19, "S");
codes.put(20, "T");
codes.put(21, "U");
codes.put(22, "V");
codes.put(23, "W");
codes.put(24, "X");
codes.put(25, "Y");
codes.put(26, "Z");
}
public List<String> createCombinations(int num) {
List<String> results = new ArrayList<>();
if (num <= 9 && num >= 0) {
results.add(codes.get(num));
} if(num <=26 && num >= 10) {
results.add(codes.get(num));
int lastNum = num % 10;
if(num/10 > 0) {
List<String> tempResult = createCombinations(num / 10);
tempResult.forEach((s) -> {
results.add(s + codes.get(lastNum));
});
}
} else {
int lastNum = num % 10;
int lastTwoNum = num % 100;
if(num/10 > 0) {
List<String> tempResult = createCombinations(num / 10);
tempResult.forEach((s) -> {
results.add(s + codes.get(lastNum));
});
}
if(num/100 > 0) {
List<String> tempResult2 = createCombinations(num / 100);
tempResult2.forEach((s) -> {
results.add(s + codes.get(lastTwoNum));
});
}
}
return results;
}
public static void main(String[] args) {
NumberCombination numberCombination = new NumberCombination();
List<String> results = numberCombination.createCombinations(1123);
results.forEach(System.out::println);
}
}
package geek.random;
public class PrintCombinaton {
private String getChar(String i){
return ""+ (char)(Integer.parseInt(i)+64);
}
private void printValues(String str, int i, int len, String res){
if(i >=len){
System.out.println(res);
return;
}
if(i+1<=len){
String toAdd1 = getChar(str.substring(i, i+1));
printValues(str, i+1, len, res+toAdd1);
}
if(i+2<=len){
String toAdd2 = getChar(str.substring(i,i+2));
printValues(str, i+2, len, res+toAdd2);
}
}
public static void main(String[] args) {
int i=1;
PrintCombinaton printCombinaton = new PrintCombinaton();
printCombinaton.printValues("1123", 0, 4, "");
}
}
Java working code
package geek.random;
public class PrintCombinaton {
private String getChar(String i){
return ""+ (char)(Integer.parseInt(i)+64);
}
private void printValues(String str, int i, int len, String res){
if(i >=len){
System.out.println(res);
return;
}
if(i+1<=len){
String toAdd1 = getChar(str.substring(i, i+1));
printValues(str, i+1, len, res+toAdd1);
}
if(i+2<=len){
String toAdd2 = getChar(str.substring(i,i+2));
printValues(str, i+2, len, res+toAdd2);
}
}
public static void main(String[] args) {
int i=1;
PrintCombinaton printCombinaton = new PrintCombinaton();
printCombinaton.printValues("1123", 0, 4, "");
}
}
#include <stdio.h>
static unsigned int combos;
void alpha_combos(unsigned int);
int main(void)
{
unsigned int input = 0;
printf("Please Provide Input \n");
scanf("%d",&input);
alpha_combos(input);
printf("combos = %d",combos);
return 0;
}
void alpha_combos(unsigned int num)
{
unsigned int rem_2digit = 0, rem_1digit = 0;
rem_2digit = num%100;
rem_1digit = num%10;
num = num/100;
if(num!=0)
alpha_combos(num);
if(rem_2digit <= 26)
{
if(combos != 0)
{
combos++;
}
combos++;
}
if (rem_1digit != 0)
{
combos++;
}
}
I don't understand why there are 5 combinations for 1123, can you please explain?
Here are some combos that I can extract (there are more though)
1,1,2,3
1,1,3,2
1,2,1,3
1,2,3,1
1,3,1,2
2,1,1,3
2,1,3,1
2,3,1,1
23,11
11,23
21,13
... and so on
- Adnan Ahmad March 15, 2016