CareerCup

At each index (idx) of the original string, append all possible decoded characters of string[idx] to all the possible decoded substrings generated so far.

void decode(const std::string &prefix, const std::string &s,
		int idx, DecodeMap &m, StringVector &pwds)
{
	if (prefix.length() == s.length()) {
		pwds.push_back(prefix);
		return;
	}

	char key = s[idx];

	std::string new_prefix = prefix;
	new_prefix.push_back(key);
	decode(new_prefix, s, idx+1, m, pwds);

	for (const char value: m[key]) {
		new_prefix = prefix;
		new_prefix.push_back(value);
		decode(new_prefix, s, idx+1, m, pwds);
	}
}

decode(std::string(""),  std::string("abcde"), 0, decode_map, pwd_vector);

private static String addInRange(String s, int start,int end)
{
if(start<=end)
return s.substring(start,end);
return "";
}


public static void printSeq(String str, Map<Character, List<Character>> map)
{
System.out.println(str);
int length = str.length();

StringBuffer sb ;
for(int i=0;i<length;i++)
{
sb = new StringBuffer();
char cLetter = str.charAt(i);
List<Character> list = map.get(cLetter);
sb.append(addInRange(str,0,i));

for(Character chr:list)
{
StringBuffer newSb = new StringBuffer();
newSb.append(sb);
newSb .append(chr);
newSb.append(addInRange(str,i+1,length));
System.out.println(newSb.toString());
}
}

}

static void printPassword(Dictionary<char, List<char>> map, String str, int index, string password)
{
if (str.Length == password.Length)
{
Console.WriteLine(password);
return;
}
char c;
if (index < str.Length)
{
c = str[index];
}
else
return;

foreach (char x in map[c])
{
password += x;
printPassword(map, str, index + 1, password);
password= password.Remove(password.Length - 1);
}


}

If anyone remembers the phone digit problem, this is the same concept basically.

I suspect this problem is actually to assess complexity analysis skills.

So the complexity on this problem is pretty huge, right?
potentially you are having to loop through the characters provided in your first string, I guess we can say for each character -> it has n encodings.

My problem appears to represent recurrence relation
T(n-1) + O(n^2) = O(n^3) ... does that seem right?

I may have to look this up.
I agree with the previous comments, this problem is exactly like the phone dialer problem.

public List<String> generatePasswords(String password, Map<Character, List<Character>> encodings)
	{
		List<String> results = new ArrayList<String>();
		
		if(password.isEmpty())
		{
			results.add("");
			return results;
		}
		
		//get the encodings of the first character, iterate for all encodings create passwords
		char firstChar = password.charAt(0);
		List<Character> firstCharEncodings = encodings.get(firstChar);
		
		
		//firstCharEncodings.add(firstChar);
		List<String> words = generatePasswords(password.substring(1), encodings);
		
		for(String word: words)
		{
			String result = firstChar + word;
			results.add(result);
		}
		
		for(Character firstCharEncoding : firstCharEncodings)
		{
			String result = "";
			for(String word: words)
			{
				result = firstCharEncoding + word;
				results.add(result);
			}
			
		}
		
		return results;
	}

Map<Character, List<Character>> encodings = new HashMap<Character, List<Character>>();
		encodings.put('a', Arrays.asList('1','2','p','o','q'));
		encodings.put('b', Arrays.asList('2','y'));
		encodings.put('c', Arrays.asList('p'));
		encodings.put('d', Arrays.asList('4','a','m','n'));
		encodings.put('e', Arrays.asList('9','z','x'));
		List<String> generatedPasswords = newObj.generatePasswords("abcde", encodings);
		System.out.println(Arrays.toString(generatedPasswords.toArray()));

How about the following approach using a recursive worker to preserve extra space for passing references?

public static ArrayList<String> getEncodings(Map<Character, Collection<Character>> charMap, String str){
  //handle the invalid conditions
  if(str == null || charMap == null){
    throw new NullPointerException();
  }
  if(str.isEmpty()){
    return str;
  }
  
  //construct a recursive worker
  EncodingBuilder builder = new EncodingBuilder(charMap, str);
  //execute it
  builder.execute();
  //return the results
  return builder.results;
}

private static class EncodingBuilder{
  Map<Character, Collection<Character>> charMap;
  StringBuilder resultBuilder;
  ArrayList<String> results;
  char[] strChars;

  EncodingBuilder(Map<Character, Collection<Character> charMap, String str){
    this.charMap = charMap;
    this.resultBuilder = new StringBuilder();
    this.results = new ArrayList<String>();
    this.strChars = str.getChars();
  }
  
  private void execute(){
    int index = this.resultBuilder.length();
    //if all characters have been translated, add as a result
    if(index == strChars.length){
      this.results.add(this.resultBuilder.toString());
      return;
    }
    //otherwise, consider untranslated char
    this.resultBuilder.append(this.strChars[index]);
    //go to the next position
    execute(index+1);
    //remove untranslated char
    this.resultBuilder.setLength(index);
    //get all possible encodings
    Collection<Character> encodings = charMap.get(this.strChars[index]);
    //if the encodings exist
    if(encodings != null){
      //for each such encoding
      for(Character c : encodings){
        //add the considered character
        this.resultBuilder.append(c);
        //check the next index
        execute(index + 1);
        //remove the considered character
        this.resultBuilder.setLength(index);
      }
    }
  }
}

This problem can be solved using permutation.
In the decoded string

the first position can be filled using 5 ways as the first letter is 'a'
the 2nd position can be filled 2 ways as the second letter is 'b'
the 3rd position can be filled using 1 way as the 3rd letter is 'c'
the 4th position can be filled using 4 ways as the 4th letter is 'd'
the 5th position can be filled using 3 ways as the 5th letter is 'e'

hence the possible passwords are 5*2*1*4*3 = 120 passwords.

thats right..

How about this? It runs much faster (several times) than recursive algorithm.

static void run2(Dictionary<char, char[]> dict, string input, List<string> output)
		{
			int[] indexes = new int[input.Length];
			int[] limits = new int[input.Length];
			for (int i = 0; i < indexes.Length; i++)
			{
				indexes[i] = -1;
				limits[i] = dict.ContainsKey(input[i]) ? dict[input[i]].Length-1 : -1;
			}

			bool stop = false;
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < indexes.Length; i++)
			{
				sb.Append(indexes[i] < 0 ? input[i] : dict[input[i]][indexes[i]]);
			}
			while (!stop)
			{
				output.Add(sb.ToString());
				//Console.WriteLine(sb);
				indexes[0]++;
				for (int i = 0; i < indexes.Length; i++)
				{
					if (indexes[i] > limits[i])
					{
						indexes[i] = -1;
						sb[i] = input[i];
						if (i < indexes.Length - 1)
						{
							indexes[i + 1]++;
						}
						else
							stop = true;
					}
					else
					{
						sb[i] = dict[input[i]][indexes[i]];
						break;
					}
				}
			}
		}

Use recursion

dict1={'a':[1,2,'p','o','q'],'b':[2,'y'],'c':['p'],'d':[4,'a','m','n'],'e':[9,'z','x']}
str1="abcde"
def doJob(str1,i,l,dict1):
  if i<l:
    for j in dict1[str1[i]]:
      print str1
      temp=str1[i]
      str1=str1.replace(temp,str(j))
      doJob(str1,i+1,l,dict1)
doJob(str1,0,len(str1),dict1)

output=>
abcde
1bcde
12cde
12pde
12p4e
12p49
12p4z
12p4e
12pae
12pa9
12paz
12pae
12pme
12pm9
12pmz
12pme
12pne
12pn9
12pnz
12cde
1ycde
1ypde
1yp4e
1yp49
1yp4z
1yp4e
1ypae
1ypa9
1ypaz
1ypae
1ypme
1ypm9
1ypmz
1ypme
1ypne
1ypn9
1ypnz
1bcde
2bcde
22cde
22pde
22p4e
22p49
22p4z
22p4e
22pae
22pa9
22paz
22pae
22pme
22pm9
22pmz
22pme
22pne
22pn9
22pnz
22cde
yycde
yypde
yyp4e
yyp49
yyp4z
yyp4e
yypae
yypa9
yypaz
yypae
yypme
yypm9
yypmz
yypme
yypne
yypn9
yypnz
2bcde
pbcde
p2cde
p2pde
p2p4e
p2p49
p2p4z
p2p4e
p2pae
p2pa9
p2paz
p2pae
p2pme
p2pm9
p2pmz
p2pme
p2pne
p2pn9
p2pnz
p2cde
pycde
pypde
pyp4e
pyp49
pyp4z
pyp4e
pypae
pypa9
pypaz
pypae
pypme
pypm9
pypmz
pypme
pypne
pypn9
pypnz
pbcde
obcde
o2cde
o2pde
o2p4e
o2p49
o2p4z
o2p4e
o2pae
o2pa9
o2paz
o2pae
o2pme
o2pm9
o2pmz
o2pme
o2pne
o2pn9
o2pnz
o2cde
oycde
oypde
oyp4e
oyp49
oyp4z
oyp4e
oypae
oypa9
oypaz
oypae
oypme
oypm9
oypmz
oypme
oypne
oypn9
oypnz
obcde
qbcde
q2cde
q2pde
q2p4e
q2p49
q2p4z
q2p4e
q2pae
q2pa9
q2paz
q2pae
q2pme
q2pm9
q2pmz
q2pme
q2pne
q2pn9
q2pnz
q2cde
qycde
qypde
qyp4e
qyp49
qyp4z
qyp4e
qypae
qypa9
qypaz
qypae
qypme
qypm9
qypmz
qypme
qypne
qypn9
qypnz