Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
import java.util.*;
public class Solution {
public static void main(String[] args) {
Map<String, String[]> m = new HashMap<String, String[]>();
m.put("1", new String[] { "A", "B", "C" });
m.put("2", new String[] { "D", "E" });
m.put("12", new String[] { "X" });
m.put("3", new String[] { "P", "Q" });
String string = "123";
List<String> keys = new ArrayList<String>(m.keySet());
List<String> patterns = new ArrayList<String>();
for (int i = 0; i < keys.size(); i++) {
if(!string.startsWith(keys.get(i))) {
continue;
}
List<String> keyList = new ArrayList<String>();
keyList.add(keys.get(i));
String tmp = string.substring(keys.get(i).length());
int j = i + 1;
// checking of 'j' is important, otherwise it will be infinite loop if given string is not found
while (!tmp.isEmpty() && j < keys.size()) {
for (; j < keys.size(); j++) {
if (tmp.startsWith(keys.get(j))) {
tmp = tmp.substring(keys.get(j).length());
keyList.add(keys.get(j));
break;
}
}
}
if(!stringFound(string,keyList)) {
continue;
}
patterns.addAll(generatePatterns(m, keyList));
}
System.out.println(patterns.toString());
}
private static List<String> generatePatterns(Map<String, String[]> m, List<String> keyList) {
List<String> patterns = new ArrayList<String>();
for(String key: keyList) {
if (patterns.size() == 0) {
patterns.addAll(Arrays.asList(m.get(key)));
continue;
}
List<String> tmpPatterns = new ArrayList<String>();
String[] candidateArr = m.get(key);
for (String pattern : patterns) {
for(String candidate : candidateArr) {
tmpPatterns.add(pattern.concat(candidate));
}
}
patterns = tmpPatterns;
}
return patterns;
}
private static boolean stringFound(String string, List<String> keyList) {
String str ="";
for(String key : keyList) {
str += key;
}
return str.equals(string);
}
}
package main
import (
"fmt"
"strings"
)
func patterns(m map[string][]string, str string) []string {
res := []string{}
if len(str) == 0 {
return []string{""}
}
for k := range m {
if strings.HasPrefix(str, k) {
for _, kv := range m[k] {
ends := patterns(m, str[len(k):])
for _, e := range ends {
res = append(res, kv+e)
}
}
}
}
return res
}
func main() {
m := map[string][]string{
"1": {"A", "B", "C"},
"2": {"D", "E"},
"12": {"X"},
"3": {"P", "Q"},
}
fmt.Println(patterns(m, "123"))
}
class findPattern:
def __init__(self, indices):
self.indices = indices
def compute(self, str):
if not len(str):
return {}
i = 0
c_ret = set()
for i,c in enumerate(str):
if str[0:i+1] in self.indices:
s = str[0:i+1]
res = self.compute(str[i+1:])
for x in self.indices[s]:
if not len(res):
c_ret.add(x)
else:
for y in res:
c_ret.add(x+y)
return c_ret
X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q']}
P = findPattern(X)
print list(P.compute('123'))
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
std::vector<std::string> collect(std::unordered_map<std::string, std::list<std::string>> & data, const std::string & part)
{
std::vector<std::string> results;
for (int i = 1; i <= part.length(); i++) {
std::string s = part.substr(0, i);
auto it = data.find(s);
if (it != data.end()) {
if (s.length() == part.length()) {
for (auto && it3 : it->second) {
results.push_back(it3);
}
}
else {
std::string h = part.substr(i, part.length() - i);
std::vector<std::string> sub_results = collect(data, h);
for (auto && it3 : it->second) {
for (auto && it2 : sub_results) {
results.push_back(it3 + it2);
}
}
}
}
}
return results;
}
int main()
{
std::unordered_map<std::string, std::list<std::string>> data;
data["1"].push_back("A");
data["1"].push_back("B");
data["1"].push_back("C");
data["2"].push_back("D");
data["2"].push_back("E");
data["12"].push_back("X");
data["3"].push_back("P");
data["3"].push_back("Q");
std::vector<std::string> results = collect(data, "123");
for (auto && it2 : results) {
std::cout << it2 << " ";
}
return 0;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class AllPossiblePatterns {
public static void main(String[] args) {
// TODO Auto-generated method stub
HashMap<String, char[]> map = new HashMap<>();
char arr1[]={'A', 'B', 'C'};
map.put("1", arr1);
char arr2[]={'D', 'E'};
map.put("2", arr2);
char arr3[]={'X'};
map.put("12", arr3);
char arr4[]={'P', 'Q'};
map.put("3", arr4);
printallpatters(map, "123");
}
private static void printallpatters(HashMap<String, char[]> map, String input) {
// TODO Auto-generated method stub
List<String> result = new ArrayList<>();
helper(result, new StringBuffer(), input, map, 0 );
System.out.println(result);
}
private static void helper(List<String> result, StringBuffer temp, String input,
HashMap<String, char[]> map,
int pos) {
if(pos == input.length()){
result.add(new String(temp));
return;
}
char branches[] = map.get(String.valueOf(input.charAt(pos)));
if(branches!=null){
for(int i=0;i<branches.length;i++) {
temp.append(branches[i]);
helper(result, temp, input, map, pos+1);
temp.deleteCharAt(temp.length()-1);
}
}
if(pos+2 <= input.length()){
//System.out.println(input.substring(pos, pos+2));
branches = map.get(input.substring(pos, pos+2));
if(branches!=null){
//System.out.println(branches);
for(int i=0;i<branches.length;i++) {
temp.append(branches[i]);
helper(result, temp, input, map, pos+2);
temp.deleteCharAt(temp.length()-1);
}
}
}
}
}
def get_patterns(digit, s=0):
values = {'1': ['A', 'B', 'C'],
'2': ['D', 'E'],
'12': ['X'],
'3': ['P', 'Q']}
if s == len(digit)-1:
return values.get(digit[s], [])
res = list()
for i in range(s, len(digit)-1):
sub_p = get_patterns(digit, i+1)
for l1 in sub_p:
for l2 in values.get(digit[s:i+1], []):
res.append(l2+l1)
return res
print(get_patterns('123'))
Inspired by @dmitry.labutin this is a Java version of that solution:
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
public class Solution{
public List<String> patterns(Map<String,String[]> m, String str) {
List<String> res = new ArrayList<String>();
if (str.length() == 0){
return res;
}
for (String k : m.keySet()) {
if (str.startsWith(k)) {
for(String kv : m.get(k)) {
String strSubstr = str.substring(k.length());
if((strSubstr.length() == 0)) res.add(kv);
else {
List<String> ends = patterns(m, strSubstr);
for (String e : ends) {
res.add(kv+e);
}
}
}
}
}
return res;
}
public static void main(String[] args) {
Map<String, String[]> m1 = new HashMap<String, String[]>();
m1.put("1", new String[]{"A","B","C"});
m1.put("2", new String[]{"D","E"});
m1.put("12", new String[]{"X"});
m1.put("3", new String[]{"P","Q"});
Solution sol = new Solution();
List<String> out = sol.patterns(m1, "123");
for(String s : out){
System.out.println(s);
}
}
}
Scala
object Patterns extends App {
val transforms = List(
("1", "ABC"),
("2", "DE"),
("3", "PQ"),
("12", "X"))
println(patterns("123"))
def conversions(str: String, agg: List[String] = List.empty): List[List[String]] = {
if (str.length == 0) return List(agg)
transforms.flatMap { case (from, to) =>
if (str.startsWith(from)) {
conversions(str.substring(from.length), agg :+ to)
} else {
List.empty
}
}
}
def combinations(lst: List[String], agg: String = ""): List[String] = lst match {
case "" :: rest => combinations(rest, agg)
case str :: rest => str.flatMap(c => combinations(rest, agg + c)).toList
case _ => List(agg)
}
def patterns(input: String) = conversions(input).flatMap(combinations(_))
}
input_str = '123'
# input_str = '1'
d = {
'1' : ['A', 'B', 'C'],
'2' : ['D', 'E'],
'12' : ['X'],
'3' : ['P', 'Q']
}
def permute(res_str, in_str):
if in_str == '':
print(res_str)
return
# get letter or multiple of them
for i in range(1, len(in_str)+1):
key = in_str[:i]
if key in d:
# print('key found', key)
for item in d[key]:
permute(res_str + item, in_str[i:])
permute(res_str='',in_str=input_str)
vector<string> getPermutation(map<string, vector<char>> input, string value) {
vector<string> values;
vector<string> result, output;
string currConcat, currStr;
int index = 0, len = 1;
result.push_back("");
while (index < value.length()) {
if (index + len <= value.length())
currStr = value.substr(index, len);
else
currStr = value.substr(index);
if (input.find(currStr) != input.end()) {
vector<char> current = input[currStr];
vector<string> temp;
for (char c : current) {
for (int i = 0; i < result.size(); i++) {
string res;
res += result[i];
res.push_back(c);
temp.push_back(res);
}
}
currConcat += currStr;
result = temp;
}
if (currConcat == value) {
index = 0;
len++;
currConcat = "";
output = result;
result.clear();
result.push_back("");
} else {
index += len;
}
}
return output;
}
// 123, map 1 - > {A,B,C} 2->{D,E}, 12->{X}, 3->{P,Q}
// AEP...., XP, XQ
vector<string> getPermutation(map<string, vector<char>> input, string value) {
if (input.find(value) != input.end()) {
vector<string> result;
for (auto c : input[value]) {
string temp;
temp.push_back(c);
result.push_back(temp);
}
return result;
}
vector<string> result;
for (int i = 1; i < value.length(); i++) {
vector<string> p1 = getPermutation(input, value.substr(0 ,i));
vector<string> p2 = getPermutation(input, value.substr(i));
for (auto c1 : p1) {
for (auto c2 : p2) {
string temp (c1 + c2);
result.push_back(temp);
}
}
}
return result;
}
void recurse(unordered_map<int, string> s, vector<int> indices, int ind, int n, vector<string>& result, string str)
{
if (ind >= n) return;
if (ind == 0) str.clear();
string temp = s.find(indices[ind])->second;
string::iterator it = temp.begin();
while (it!=temp.end())
{
if (ind == n - 1)
result.push_back(str + *it);
recurse(s, indices, ind + 1, n, result, str + *it);
it++;
}
}
void permutations(unordered_map<int, string> s, vector<int> indices)
{
string temp;
int n = indices.size();
vector<string> result;
recurse(s, indices, 0, n, result, temp);
for (auto i : result)
cout << i << " ";
}
int main() {
vector<int> indices = {1,2, 3};
unordered_map<int, string> strs;
strs.insert({ 1, "ABC" });
strs.insert({ 2, "DE" });
strs.insert({ 12, "X" });
strs.insert({ 3, "PQ" });
permutations(strs, indices);
return 0;
}
// javascript solution
let obj = {
a: ["A", "B", "C"],
b: ["D", "E"],
ab: ["X"],
c: ["Q", "P"]
};
let final = [];
const patterns = (str, prefix='') => {
if (str === '') {
if (prefix.length > 0) final.push(prefix);
return;
}
for (let i = 1; i <= str.length; i++) {
let subprefix = str.slice(0,i);
if (obj.hasOwnProperty(subprefix)) {
obj[subprefix].forEach(e => {
patterns(str.slice(i), prefix + e);
});
}
}
}
patterns('abc');
func find(_ digits: [Character]) -> [String] {
var result = [String]()
let map = ["1": ["A","B","C"], "2": ["D","E"], "12": ["X"], "3": ["P", "Q"]]
var dp = [[String]](repeating:[String](repeating:"", count: 0), count: digits.count+1)
dp[0] = []
for i in stride(from: 0, to: digits.count, by: 1) {
result.removeAll()
if i == 0 {
//only single
var chars = map[String(digits[i])]!
chars.forEach {
result.append(String($0))
}
dp[i+1] = result
} else {
var partialResult = dp[i]
//ones
let ones = map[String(digits[i])]!
for pr in partialResult {
for one in ones {
result.append(pr + String(one))
}
}
let twoKey = String("\(digits[i-1])\(digits[i])")
if ["12"].contains(twoKey) {
var partialResult = dp[i-1]
let twos = map[twoKey]!
if i == 1 {
twos.forEach {
result.append(String($0))
}
} else{
for pr in partialResult {
for two in twos {
result.append(pr + String(two))
}
}
}
}
dp[i+1] = result
}
}
return dp[digits.count]
}
package poc;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
/**
*
* @author Nalin
*
*/
public class PatternAgain {
/*
* output [adp, adq, aep, aeq, bdp, bdq, bep, beq, cdp, cdq, cep, ceq, xp, xq]
*/
public static void main(String[] args) {
Map<String, List<Character>> map = new HashMap<>();
map.put("1", Arrays.asList('a', 'b', 'c'));
map.put("2", Arrays.asList('d', 'e'));
map.put("12", Arrays.asList('x'));
map.put("3", Arrays.asList('p', 'q'));
String s = "123";
List<String> l = new ArrayList<>();
char[] arr = s.toCharArray();
for (char a : arr) {
l.add(String.valueOf(a));
}
Set<List<String>> combinations = new HashSet<>();
combinations.add(l);
rec(s, l, combinations);
// all the combinations generated
List<List<String>> list = new ArrayList<>(combinations);
List<String> out = new ArrayList<>();
//combinations.forEach(System.out::println);
// please bear learning java 8, but it's not very java 8ish, filtering
// combinations
list = list.stream().filter((List<String> innerList) -> {
boolean[] toConsider = { true };
innerList.stream().forEach(item -> {
if (!map.containsKey(item)) {
toConsider[0] = false;
}
});
return toConsider[0];
}).collect(Collectors.toList());
// finding all outputs
sol(out, map, 0, list, 0);
System.out.println(out);
}
private static void sol(List<String> out, Map<String, List<Character>> map, int ind, List<List<String>> list,
int i) {
if (i < list.size()) {
innerSol(list.get(i), 0, map, list.get(i).size(), out, "");
sol(out, map, ind, list, i + 1);
}
}
private static void innerSol(List<String> combinations, int c, Map<String, List<Character>> map, int size,
List<String> out, String str) {
if (c == size) {
// collect
out.add(str);
} else {
String match = combinations.get(c);
List<Character> givenChars = map.get(match);
for (int k = 0; k < givenChars.size(); k++) {
String nStr = str + givenChars.get(k);
innerSol(combinations, c + 1, map, size, out, nStr);
}
}
}
private static void rec(String s, List<String> l, Set<List<String>> combinations) {
// check for corresponding words with this list
// variants
for (int i = 0; i < l.size(); i++) {
if (i < l.size() - 1) {
String a = l.get(i);
String b = l.get(i + 1);
List<String> nl = new ArrayList<>(l);
nl.remove(i);
nl.set(i, a + b);
combinations.add(nl);
rec(s, nl, combinations);
}
}
}
}
package poc;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
/**
*
* @author Nalin
*
*/
public class PatternAgain {
/*
* output [adp, adq, aep, aeq, bdp, bdq, bep, beq, cdp, cdq, cep, ceq, xp, xq]
*/
public static void main(String[] args) {
Map<String, List<Character>> map = new HashMap<>();
map.put("1", Arrays.asList('a', 'b', 'c'));
map.put("2", Arrays.asList('d', 'e'));
map.put("12", Arrays.asList('x'));
map.put("3", Arrays.asList('p', 'q'));
String s = "123";
List<String> l = new ArrayList<>();
char[] arr = s.toCharArray();
for (char a : arr) {
l.add(String.valueOf(a));
}
Set<List<String>> combinations = new HashSet<>();
combinations.add(l);
rec(s, l, combinations);
// all the combinations generated
List<List<String>> list = new ArrayList<>(combinations);
List<String> out = new ArrayList<>();
//combinations.forEach(System.out::println);
// please bear learning java 8, but it's not very java 8ish, filtering
// combinations
list = list.stream().filter((List<String> innerList) -> {
boolean[] toConsider = { true };
innerList.stream().forEach(item -> {
if (!map.containsKey(item)) {
toConsider[0] = false;
}
});
return toConsider[0];
}).collect(Collectors.toList());
// finding all outputs
sol(out, map, 0, list, 0);
System.out.println(out);
}
private static void sol(List<String> out, Map<String, List<Character>> map, int ind, List<List<String>> list,
int i) {
if (i < list.size()) {
innerSol(list.get(i), 0, map, list.get(i).size(), out, "");
sol(out, map, ind, list, i + 1);
}
}
private static void innerSol(List<String> combinations, int c, Map<String, List<Character>> map, int size,
List<String> out, String str) {
if (c == size) {
// collect
out.add(str);
} else {
String match = combinations.get(c);
List<Character> givenChars = map.get(match);
for (int k = 0; k < givenChars.size(); k++) {
String nStr = str + givenChars.get(k);
innerSol(combinations, c + 1, map, size, out, nStr);
}
}
}
private static void rec(String s, List<String> l, Set<List<String>> combinations) {
// check for corresponding words with this list
// variants
for (int i = 0; i < l.size(); i++) {
if (i < l.size() - 1) {
String a = l.get(i);
String b = l.get(i + 1);
List<String> nl = new ArrayList<>(l);
nl.remove(i);
nl.set(i, a + b);
combinations.add(nl);
rec(s, nl, combinations);
}
}
}
}
package poc;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
/**
*
* @author Nalin
*
*/
public class PatternAgain {
/*
* output [adp, adq, aep, aeq, bdp, bdq, bep, beq, cdp, cdq, cep, ceq, xp, xq]
*/
public static void main(String[] args) {
Map<String, List<Character>> map = new HashMap<>();
map.put("1", Arrays.asList('a', 'b', 'c'));
map.put("2", Arrays.asList('d', 'e'));
map.put("12", Arrays.asList('x'));
map.put("3", Arrays.asList('p', 'q'));
String s = "123";
List<String> l = new ArrayList<>();
char[] arr = s.toCharArray();
for (char a : arr) {
l.add(String.valueOf(a));
}
Set<List<String>> combinations = new HashSet<>();
combinations.add(l);
rec(s, l, combinations);
// all the combinations generated
List<List<String>> list = new ArrayList<>(combinations);
List<String> out = new ArrayList<>();
//combinations.forEach(System.out::println);
// please bear learning java 8, but it's not very java 8ish, filtering
// combinations
list = list.stream().filter((List<String> innerList) -> {
boolean[] toConsider = { true };
innerList.stream().forEach(item -> {
if (!map.containsKey(item)) {
toConsider[0] = false;
}
});
return toConsider[0];
}).collect(Collectors.toList());
// finding all outputs
sol(out, map, 0, list, 0);
System.out.println(out);
}
private static void sol(List<String> out, Map<String, List<Character>> map, int ind, List<List<String>> list,
int i) {
if (i < list.size()) {
innerSol(list.get(i), 0, map, list.get(i).size(), out, "");
sol(out, map, ind, list, i + 1);
}
}
private static void innerSol(List<String> combinations, int c, Map<String, List<Character>> map, int size,
List<String> out, String str) {
if (c == size) {
// collect
out.add(str);
} else {
String match = combinations.get(c);
List<Character> givenChars = map.get(match);
for (int k = 0; k < givenChars.size(); k++) {
String nStr = str + givenChars.get(k);
innerSol(combinations, c + 1, map, size, out, nStr);
}
}
}
private static void rec(String s, List<String> l, Set<List<String>> combinations) {
// check for corresponding words with this list
// variants
for (int i = 0; i < l.size(); i++) {
if (i < l.size() - 1) {
String a = l.get(i);
String b = l.get(i + 1);
List<String> nl = new ArrayList<>(l);
nl.remove(i);
nl.set(i, a + b);
combinations.add(nl);
rec(s, nl, combinations);
}
}
}
}
Simple Solution by recursion.
Go character by character on the input number (eg. 123)
In first run we will have current=1, and the mapping for it is ['A', 'B', 'C']
Now, for each of the element in the array we want to get the suffix which if found by doing recursion on the remainder of the input number (substring(i + 1))
Pretty straightforward.
public class GenerateString {
private static Map<String, char[]> map = new HashMap<>();
static {
map.put("1", new char[]{'A', 'B', 'C'});
map.put("2", new char[]{'D', 'E'});
map.put("3", new char[]{'P', 'Q'});
map.put("12", new char[]{'X'});
}
public static void main(String[] args) {
System.out.println(convertToString("123"));
}
public static List<String> convertToString(String numStr) {
List<String> result = new ArrayList<>();
if(numStr == null || numStr.length() == 0 ) { result.add("");}
for(int i = 0; i < numStr.length(); i++) {
String current = numStr.substring(0, i+1);
if(map.containsKey(current)) {
char[] chars = map.get(current);
for(char ch : chars) {
for(String t : convertToString(numStr.substring(i + 1))) {
result.add(ch + t);
}
}
}
}
return result;
}
}
Simple Solution by recursion.
Go character by character on the input number (eg. 123)
In first run we will have current=1, and the mapping for it is ['A', 'B', 'C']
Now, for each of the element in the array we want to get the suffix which if found by doing recursion on the remainder of the input number (substring(i + 1))
Pretty straightforward.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class GenerateString {
private static Map<String, char[]> map = new HashMap<>();
static {
map.put("1", new char[]{'A', 'B', 'C'});
map.put("2", new char[]{'D', 'E'});
map.put("3", new char[]{'P', 'Q'});
map.put("12", new char[]{'X'});
}
public static void main(String[] args) {
System.out.println(convertToString("123"));
}
public static List<String> convertToString(String numStr) {
List<String> result = new ArrayList<>();
if(numStr == null || numStr.length() == 0 ) { result.add("");}
for(int i = 0; i < numStr.length(); i++) {
String current = numStr.substring(0, i+1);
if(map.containsKey(current)) {
char[] chars = map.get(current);
for(char ch : chars) {
for(String t : convertToString(numStr.substring(i + 1))) {
result.add(ch + t);
}
}
}
}
return result;
}
}
import java.util.HashMap;
import java.util.Map;
public class EnumeratePatterns {
public static void main(String[] args){
// testcase
Map<String, char[]> dict = new HashMap<String, char[]>();
dict.put("1", new char[] {'A', 'B', 'C'});
dict.put("2", new char[] {'D', 'E'});
dict.put("12", new char[] {'X'});
dict.put("3", new char[] {'P', 'Q'});
enumerate("123", dict);
}
public static void enumerate(String inp, Map<String,char[]> dict) {
enumerate(inp.toCharArray(), "", 0, inp.length(), dict);
}
public static void enumerate(char[] inp, String prefix, int begin, int n, Map<String,char[]> dict) {
// base case
if (begin == n){
System.out.println(prefix);
}
// extend prefix
String key = "";
for (int i = begin; i < n; i++){
if(dict.containsKey(key + inp[i])){
key = key + inp[i];
char[] values = dict.get(key);
for (char c : values){
String extendedPrefix = prefix + c;
enumerate(inp, extendedPrefix, i+1, n, dict);
}
}
}
}
}
package main
import (
"fmt"
)
var arr = map[string][]string {
"1" : {"A", "B", "C"},
"2" : {"D", "E"},
"12" : {"X"},
"3" : {"P", "Q"},
}
func gen(p string, cur string) {
if p == "" {
fmt.Println(cur)
} else {
for i := 1; i <= len(p); i++ {
for _, n := range arr[p[:i]] {
gen(p[i:], cur + n)
}
}
}
}
func main() {
gen("123", "")
}
package main
import (
"fmt"
)
var arr = map[string][]string {
"1" : {"A", "B", "C"},
"2" : {"D", "E"},
"12" : {"X"},
"3" : {"P", "Q"},
}
func gen(p string, cur string) {
if p == "" {
fmt.Println(cur)
} else {
for i := 1; i <= len(p); i++ {
for _, n := range arr[p[:i]] {
gen(p[i:], cur + n)
}
}
}
}
func main() {
gen("123", "")
}
package main
import (
"fmt"
)
var arr = map[string][]string {
"1" : {"A", "B", "C"},
"2" : {"D", "E"},
"12" : {"X"},
"3" : {"P", "Q"},
}
func gen(p string, cur string) {
if p == "" {
fmt.Println(cur)
} else {
for i := 1; i <= len(p); i++ {
for _, n := range arr[p[:i]] {
gen(p[i:], cur + n)
}
}
}
}
func main() {
gen("123", "")
}
func getValue(_ input: String) -> [String] {
var nodeList = [Node<Dictionary<String, [[String]]>>]()
var tempArray = [[String]]()
let dictionary = ["1": ["A", "B", "C"], "2": ["D", "E"], "12": ["X"], "3": ["P", "Q"]]
for character in input {
if let values = dictionary[String(character)] {
tempArray.append(values)
}
}
let node = Node(list: [input: tempArray])
nodeList.append(node)
tempArray = [[String]]()
var j = 0
for i in stride(from: 2, to: input.count, by: 2) {
j = i
if let values = dictionary[String(input[input.startIndex ..< input.index(input.startIndex, offsetBy: i)])] {
tempArray.append(values)
}
}
while j < input.count {
j += 1
if let values = dictionary[String(j)] {
tempArray.append(values)
}
}
nodeList.append(Node(list: [input: tempArray]))
var finalArray = [String]()
var resultArray = [String]()
for node in nodeList {
resultArray = [String]()
for values in node.list[input]! {
if resultArray.isEmpty {
resultArray = values
} else {
var temp = [String]()
for value in values {
for result in resultArray {
temp.append("\(result)\(value)")
}
}
resultArray = temp
}
}
finalArray += resultArray
}
return finalArray
}
class Node<T> {
let list: T
init(list: T) {
self.list = list
}
}
Here is my solution, works in all corner cases... well tested
public class ListCombination {
public static void main(String args[]) {
Map<String, char[]> input = new HashMap<>();
input.put("1", new char[]{'A', 'B', 'C'});
input.put("2", new char[]{'D', 'E'});
input.put("3", new char[]{'P', 'Q'});
input.put("12", new char[]{'X'});
input.put("4", new char[]{'T', 'S'});
input.put("23", new char[]{'Z', 'N'});
input.put("34", new char[]{'O', 'M'});
input.put("234", new char[]{'W', 'Y'});
input.put("1234", new char[]{'@', '#'});
String test = "1234";
try {
List<String> output = generateCombination(input, test);
System.out.println(output);
} catch (InvalidArgument invalidArgument) {
invalidArgument.printStackTrace();
}
}
private static List<String> generateCombination(Map<String, char[]> input, String test) throws InvalidArgument {
if (null == input || input.isEmpty() || null == test || test.isEmpty())
return Collections.EMPTY_LIST;
//Build list of string that need to traverse recursively
List<List<String>> considerList = buildConsiderList(input, test);
return considerList.stream().map(list -> generateCombination(list)).flatMap(Collection::stream).collect(Collectors.toList());
}
private static List<List<String>> buildConsiderList(Map<String, char[]> input, String pattern) throws InvalidArgument {
List<List<String>> toConsider = new LinkedList<>();
/**
* Consider of key;
* Here we use key a loop runner because we could have case where from pattern multiple (off different size) string present in input map,
* then if we traverse over pattern then we need to generate n^2 sub string and check all of them in map, that corresponding list present or not
*/
for (String key : input.keySet()) {
List<String> subListsToConsider = new ArrayList<>();
//If this key does not include in the first place of the pattern list, then don't consider all list by it
//Example: Key = 2, pattern=123 -> since 123 does not start with 2, which means all the list by 2 we can't consider since it has to be like 123
if (!pattern.startsWith(key))
continue;
//process for current key array
char[] current = input.get(key);
subListsToConsider.add(new String(current));
//Take the remaining length to consider
//example key = 1, pattern=123, then remaining is = 23 which we'll consider one by one
String remainingPattern = pattern.substring(key.length());
//Case 1: character by character
//process remaining
for (int i = 0; i < remainingPattern.length(); i++) {
//if this does not present in input; input is corrupt
if (!input.containsKey(String.valueOf(remainingPattern.charAt(i))))
throw new InvalidArgument("Input " + pattern + "is invalid");
char[] temp = input.get(String.valueOf(remainingPattern.charAt(i)));
subListsToConsider.add(new String(temp));
}
//case 2: whole remaining list
if (remainingPattern.length() > 1 && input.containsKey(remainingPattern)) {
List<List<String>> withRemaining = new ArrayList<>();
List<String> rem = new ArrayList<>();
rem.add(new String(input.get(key)));
rem.add(new String(input.get(remainingPattern)));
withRemaining.add(rem);
toConsider.addAll(withRemaining);
}
toConsider.add(subListsToConsider);
}
return toConsider;
}
private static List<String> generateCombination(List<String> input) {
List<String> output = new LinkedList<>();
generateCombination(input, 0, output, "");
return output;
}
private static void generateCombination(List<String> input, int index, List<String> output, String temp) {
if (temp.length() == input.size()) {
output.add(temp);
return;
}
String current = input.get(index);
for (int i = 0; i < current.length(); i++) {
temp = temp + current.charAt(i);
generateCombination(input, index + 1, output, temp);
temp = temp.substring(0, temp.length() - 1);
}
}
}
def main():
X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q'], '4': ['E', 'F', 'G']}
num = 1234
l = [x for x in str(num)]
li = [X[i] for i in l]
combiA = []
for i in range (len(li)):
for j in range(len(li[i])):
recCombi(li[i][j],li, combiA, len(li), i+1)
combiA.clear()
def recCombi(x, l2, combiA, finalLen, index):
combiA.append(x)
if (len(combiA) == finalLen):
print(combiA)
return
if(index >= finalLen):
return
i = 0
j = 1 + index
for i in range (len(l2[index])):
recCombi(l2[index][i],l2, combiA, finalLen, j)
combiA.pop()
return
main()
def main():
X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q'], '4': ['E', 'F', 'G']}
num = 1234
l = [x for x in str(num)]
li = [X[i] for i in l]
combiA = []
for i in range (len(li)):
for j in range(len(li[i])):
recCombi(li[i][j],li, combiA, len(li), i+1)
combiA.clear()
def recCombi(x, l2, combiA, finalLen, index):
combiA.append(x)
if (len(combiA) == finalLen):
print(combiA)
return
if(index >= finalLen):
return
i = 0
j = 1 + index
for i in range (len(l2[index])):
recCombi(l2[index][i],l2, combiA, finalLen, j)
combiA.pop()
return
main()
- sema638 July 15, 2018public class SubCombinations { private static List<String> getCombinations(Map<String, List<String>> map, String s) { List<String> result = map.getOrDefault(s, new ArrayList<>()); for (int i=1; i<s.length(); i++) { String word = s.substring(0, i); List<String> chars = map.get(word); if (chars != null) { String rest = s.substring(i, s.length()); List<String> subs = getCombinations(map, rest); for (String ch : chars) { for (String sub : subs) { result.add(ch + sub); } } } } return result; } public static void main(String[] args) { System.out.println(getCombinations(new HashMap<String, List<String>>() {{ put("1", Arrays.asList("A", "B", "C")); put("2", Arrays.asList("D", "E")); put("12", Arrays.asList("X")); put("3", Arrays.asList("P", "Q")); }}, "123")); } }