CareerCup

The question clearly states ' return an array of all possible mutations'. This means that both time AND space must be linear in the size of the output. The point is, what is the size of the output in terms of the input.

Lets just look at the worst-case complexity, since average case is hard to even define, let alone analyse. Say the input string is of size n. The worst case is that every character has a mapping. Lets also say that all mappings have arrays of the same size, m (that is, all arrays are the longest possible arrays for that mapping). Then the number of outputs we have is n^m, which is huge.

In simple terms I can't see any way to optimise this. However, you could return a data structure like this (for the given example):

[
[f, F, 4],
[a],
[b, B, 8]
]

ie an array of arrays, where every subarray is the corresponding character, together with its mapped mutations if there are any. You could then create an iterator that uses that data structure to produce the next mutated output string from each call to next().

Treat is like an odometer: [3,1,3]. Start with [0,0,0] -> [1,0,0] -> [2,0,0] ->[0, 0, 1] -> [1,0,1] etc. (read from right to left instead left to right).

This little space (as compared to creating lists and appending).

Here is some python code:

def generate_odometer(limits_list):
	odometer_list = map(lambda x: 0, limits_list)
	has_more = True
	n = len(odometer_list)
	while has_more:
		yield odometer_list
		has_more = False
		for j in range(0,n):
			limit = limits_list[j]
			if odometer_list[j] < limit-1:
				odometer_list[j] = odometer_list[j]+1
				has_more = True
				break
			else:
				odometer_list[j] = 0;
				continue
  
def generate_mutations(string, hashmap):
	limits_list  = map(lambda c: 1 + len(hashmap[c]) if c in hashmap else 1, string)
	for odometer in generate_odometer(limits_list):
		yield odometer_string(odometer, string, hashmap) 
  
def odometer_string (odometer, string, hashmap):
	chars = map (lambda idx, ch: ch if idx == 0 else hashmap[ch][idx -1], 
			odometer, string)
	return ''.join(chars)
  	
def main():
	hashmap = {'f':['F', '4'], 'b': ['B', '8']}
	for s in generate_mutations('fab', hashmap):
		print s

output is

fab
Fab
4ab
faB
FaB
4aB
fa8
Fa8
4a8

This is my solution, I think space complexity should be O(n), Since I use backtrack, time complexity is not very well.

My output sequence is different:fab faB fa8 Fab FaB Fa8 4ab 4aB 4a8

import java.util.ArrayList;
import java.util.HashMap;

//Given a hashmap M which is a mapping of characters to arrays of substitute characters,
//and an input string S, return an array of all possible mutations of S
//(where any character in S can be substituted with one of its substitutes in M, if it exists).

public class Permute {

public static ArrayList<String> getMutation(String str, HashMap<Character, char[]> map){
ArrayList<String> result = new ArrayList<String>();
int lens = str.length();
if(lens == 0){
return result;
}
if(map.isEmpty()){
result.add(str);
return result;
}
char[] mutation = new char[lens];
getMutation(str, map, result, mutation, 0);
return result;
}

public static void getMutation(String str, HashMap<Character, char[]> map, ArrayList<String> result, char[] mutation, int index){
if(index == str.length()){
String newItem = new String(mutation);
result.add(newItem);
return;
}

char current = str.charAt(index);
if(map.containsKey(current)){
char[] choice = map.get(current);
for(int i = 0; i <= choice.length;i++){
if(i == 0){
mutation[index] = current;
getMutation(str, map,result, mutation, index+1);
}
else{
mutation[index] = choice[i-1];
getMutation(str, map, result, mutation, index+1);
}
}
}
else{
mutation[index] = current;
getMutation(str, map, result, mutation, index+1);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String in = "fab";
char[] valueOne = new char[2];
char[] valueTwo = new char[2];
HashMap<Character, char[]> map = new HashMap<Character, char[]>();
valueOne[0] = 'F';
valueOne[1] = '4';
valueTwo[0] = 'B';
valueTwo[1] = '8';
map.put('f', valueOne);
map.put('b', valueTwo);
ArrayList<String> result = new ArrayList<String>();
result = getMutation(in, map);
for(String str:result){
System.out.println(str);
}
}
}

def substitute(m, s, results=[], prefix=""):
    if not s:
        results.append(prefix)
        return results

    char = s[0]
    if char in m:
        for substitution in m[char]:
            new_prefix = prefix + substitution
            substitute(m, s[1:], results, new_prefix)
    substitute(m, s[1:], results, prefix + s[0])
    return results


M = { "f": ["F", "4"], "b": ["B", "8"] }
S = "fab"
print(substitute(M, S))

public void doIt(String s,Map<Character,Character[]> m){
		List<String> results = new ArrayList<String>();
		if(results.add(s));
		for(Character c : s.toCharArray()){
			if(M.containsKey(c)){
				List<String> list = new ArrayList<String>();
				for(Character k : M.get(c)){
					for(String temp : results){
						list.add(temp.replace(c,k));
					}
				}
				results.addAll(list);
			}
		}
		System.out.println(results);

hashmap = {'f':['F', '4'], 'b': ['B', '8']}
def printArray(str,result):
    if str == "":
        print ''.join(result)
    else:
        result.append(str[0])
        printArray(str[1:],result);
        result.pop()
        c = hashmap.get(str[0])
        if c != None:
            for r in c:
                result.append(r)
                printArray(str[1:],result);
                result.pop()
printArray("fab",[])

(function(content, htReplaceCharacters) {
    function mutate(content, index, htReplaceCharacters, result) {
        for (var i = index; i < content.length; ++i) {
            var character = content.charAt(i);

            var replaceCharacters = htReplaceCharacters[character];

            if (replaceCharacters) {
                for (var j = 0; j < replaceCharacters.length; ++j) {
                    var replaceCharacter = replaceCharacters[j];

                    var tmp = content.substr(0, i) + replaceCharacter + content.substr(i + 1);

                    result.push(tmp);

                    mutate(tmp, i + 1, htReplaceCharacters, result);
                }
            }
        }
    }

    var result = [];

    mutate(content, 0, htReplaceCharacters, result);

    result.push(content);

    console.log(result);  // "Fab", "FaB", "Fa8", "4ab", "4aB", "4a8", "faB", "fa8", "fab"
}(
    'fab',
    {
        'f': ['F', 4],
        'b': ['B', 8]
    }
));

Does anybody know the time complexity of this problem if "f" and "b" had a different number of substitutes?

My solution in Java. The time complexity is O(n^m) where n is the number of variable positions (in this case 2, f and b) and m is the number of possible values (in this case 3 for each, the letter + its substitutes).

The complexity is exponential but I don't believe we can improve on it since we are required to generate n^m output strings.

import java.util.HashMap;
import java.util.ArrayList;


public class Substitutes {

	private static HashMap<String,ArrayList<String>> substitutesMap = new HashMap<String,ArrayList<String>>();
	
	private static void permute(String permutation, String input, int pos) {
		if(pos == input.length()) {
			System.out.println(permutation);
			return;
		}

		String letter = input.substring(pos,pos+1);
		
		ArrayList<String> substitutes = new ArrayList<String>();
		substitutes.add(letter);
		if(substitutesMap.get(letter) != null)
			substitutes.addAll(substitutesMap.get(letter));

		for(String substitute : substitutes)
			permute(permutation + substitute, input, pos+1);
	}
	
	
	
	/*
	 * TEST HARNESS
	 */
	
	static {
		 ArrayList<String> f = new ArrayList<String>();
		 f.add("F");
		 f.add("4");

		 ArrayList<String> b = new ArrayList<String>();
		 b.add("B");
		 b.add("8");
		 
		 substitutesMap.put("f", f);
		 substitutesMap.put("b", b);
	};


	public static void main(String args[]) {
		permute("", "fab", 0);
	}
}

my two cents in python; i think time complexity would depend on both the size of the hashtable and the size of the input. space complexity is the same?

for i in range(len(S)):
  if i == 0:
    Oldlist = [S[i]]
    if S[i] in M:
      for j in range(len(M[S[i]])):
        Oldlist.append(M[S[i]][j])
  else:
    Newlist = []
    for m in range(len(Oldlist)):
      Newlist.append(Oldlist[m]+S[i])
      if S[i] in M:
        for n in range(len(M[S[i]])):
          Newlist.append(Oldlist[m]+M[S[i]][n])
    Oldlist = Newlist

print Oldlist

public static void printMutation(Map<Character, String> map, String str,
	    char[] ret, int cursor)
    {
	if (cursor == str.length())
	{
	    System.out.println(ret);
	    return;
	}

	Character ch = str.charAt(cursor);
	ret[cursor] = ch;
	printMutation(map, str, ret, cursor + 1);

	String mapped = map.get(ch);
	if (map.containsKey(ch))
	{
	    for (int j = 0; j < mapped.length(); j++)
	    {
		ret[cursor] = mapped.charAt(j);
		printMutation(map, str, ret, cursor + 1);
	    }
	}
    }

O(ans.count) time and O(ans.size) space complexity:

static List<string> GenerateSubstitutions(string str, Dictionary<char, string> map)
{
    List<string> result = new List<string>();
    StringBuilder sb = new StringBuilder(str);
    Action<int> rec = null;
    rec = pos =>
        {
            if (pos >= sb.Length) result.Add(sb.ToString()); 
            else
                if (!map.ContainsKey(str[pos])) rec(pos + 1);
                else
                {
                    rec(pos + 1);
                    foreach (var c in map[str[pos]])
                    {
                        sb[pos] = c;
                        rec(pos + 1);
                    }
                }
        };
    rec(0);
    return result;
}

There is also a tricky solution with very good time and space complexities. We do not have any restrictions about output format of resultant word set, so it will be absolutely legal to output them as a trie. The main idea of algorithm is following:
Given a source string and map of substitutions, let's construct a trie with a single word - source string:

(start)
       |
      (f)
       |
       |
      (a)
       |
       |
      (b)
       |
     (end)

Now, lets iterate over trie nodes. If we see a node with a character that presents in a map, let's transform this node to a cuple of nodes with all possible substitutions for that character, i.e.

|           / | \
 (f) ->  (f)(F)(4) 
  |        \ | /

Applying this procedure to all nodes, we will get a trie with all possible substitutions, like

(start)
        / | \
     (f)(F)(4)
        \ | /
          |
         (a)
          |
        / | \
    (b)(B)(8)
      /   |   \
   (end)(end)(end)

So that, in worst case, time and space complexity is O(n*k), where n is length of the string and k is length of longest array in the map of substitutions.

This code will be ok.

void Trace(std::string & path, std::vector<std::string> & rs, std::map<char, std::string> & dict, int k) {
  if (k == path.size()) {
    rs.push_back(path);
  } else {
    Trace(path, rs, dict, k + 1); 
    char ch = path[k];
    if (dict.count(ch)) {
      for (int i = 0; i < dict[ch].size(); i++) {
        path[k] = dict[ch][i];
        Trace(path, rs, dict, k + 1); 
      }   
      path[k] = ch; 
    }   
  }
}

std::vector<std::string> Trace(std::string & str, std::map<char, std::string> & dict) {
  std::vector<std::string> rs; 
  Trace(str, rs, dict, 0); 
  return rs; 
}

<?php

$in = array('f', 'a', 'b');
$hash = array(
'f' => array('F', '4'),
'b' => array('B', '8')
);

getPerm($in, $hash);

function getPerm($in, $hash)
{
	permHelper($in,sizeof($in)-1, $hash);
}

function permHelper($in,$i, $hash){
	if($i == -1)
	{
		echo "\n".implode('',$in);
		return;
	}
	
	permHelper($in,$i-1, $hash);
	
	if(isset($hash[$in[$i]]))
	{
		foreach($hash[$in[$i]] as $rep)
		{
			$in[$i] = $rep;
			permHelper($in,$i-1, $hash);			
		}
	}
}

public static void main(String[] args){
     Collection<String> results = new HashSet<>();
     getMutatedString(input, replacementMap, results);
     System.out.println(results);
}
static void getMutatedString(String input, Map<Character, List<Character>> replacements, Collection<String> results) {
		results.add(input);
		for (Character c : input.toCharArray()) {
			replacements.forEach((k, v) -> {
				if (c == k) {
					Set<String> temp = new LinkedHashSet<>();
					v.forEach(r -> results.forEach(result -> temp.add(result.replace(c, r))));
					results.clear();
					results.addAll(temp);
				}
			});
		}
	}

public class Solution{
	private static Map<Character, List<Character>> replacements = new HashMap<>();

	static {
		replacements.put('f', ImmutableList.of('F', '4'));
		replacements.put('b', ImmutableList.of('B', '8'));
	}
	static void getMutatedStrings(String input, Collection<String> results) {
		results.add(input);
		for (Character c : input.toCharArray()) {
			replacements.forEach((k, v) -> {
				if (c == k) {
					Set<String> temp = new LinkedHashSet<>();
					v.forEach(r -> results.forEach(result -> temp.add(result.replace(c, r))));
					results.clear();
					results.addAll(temp);
				}
			});
		}
	}

	public static void main(String[] args) {
		Collection<String> results = new LinkedHashSet<>();
		String input = "fab";
		getMutatedStrings(input, results);
		System.out.println(results);
	}
}

public class Solution{
	private static Map<Character, List<Character>> replacements = new HashMap<>();

	static {
		replacements.put('f', ImmutableList.of('F', '4'));
		replacements.put('b', ImmutableList.of('B', '8'));
	}
	static void getMutatedStrings(String input, Collection<String> results) {
		results.add(input);
		for (Character c : input.toCharArray()) {
			replacements.forEach((k, v) -> {
				if (c == k) {
					Set<String> temp = new LinkedHashSet<>();
					v.forEach(r -> results.forEach(result -> temp.add(result.replace(c, r))));
					results.clear();
					results.addAll(temp);
				}
			});
		}
	}

	public static void main(String[] args) {
		Collection<String> results = new LinkedHashSet<>();
		String input = "fab";
		getMutatedStrings(input, results);
		System.out.println(results);
	}
}

public static void printUtil(String input, Map<Character, Object[]> map, int ci) {
        System.out.println(input);
        if (ci >= input.length()) return;

        Object next = map.get(input.charAt(ci));
        if (next != null) {
            Object[] nextArr = (Object[]) next;
            for(int j=ci+1;j<=input.length();j++) {
                for (int i = 0; i < nextArr.length; i++) {
                    printUtil(input.substring(0,ci)+nextArr[i]+input.substring(ci+1), map, j);
                }
            }
        }
    }

    public static void print(String input, Map<Character, Object[]> map) {
//        for(int i=0;i<input.length();i++) {
            printUtil(input, map, 0);
//        }
    }

    public static void main(String[] args) {
        Map<Character, Object[]> map = new HashMap<>();
        map.put('f', new Object[]{'F', '4'});
        map.put('b', new Object[]{'B', '8'});
        print("fab", map);
    }

Time is O(N) where N is input="fab", but how many operations we have to execute?
In the worst case it is O(N*M), where M=max_length{{ 'F', '4' }, { 'B', '8' }, ...} so it is better to say that time is O(N*M).

public static void main(String[] args) {

        Map<Character, char[]> map = new HashMap<Character, char[]>();
        map.put('f', new char[] { 'F', '4' });
        map.put('b', new char[] { 'B', '8' });

        final String input = "fab";

        // expect
        // [fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]

        List<String> output = new ArrayList<String>();

        mutations(map, input, 0, output);

        // get
        // [fab, faB, fa8, Fab, FaB, Fa8, 4ab, 4aB, 4a8]
        System.out.println(output);
    }

    private static void mutations(Map<Character, char[]> map, String input, int pos, List<String> output) {
        if (pos == input.length()) {
            output.add(input);
            return;
        }

        // process 'f'
        mutations(map, input, pos + 1, output);

        // process ['F', '4']
        char ch = input.charAt(pos);
        if (map.containsKey(ch)) {
            for (char substitute : map.get(ch)) {
                input = input.replace(ch, substitute);
                mutations(map, input, pos + 1, output);
            }
        }
    }

This is a variation of telephone words:

public static void main(String[] args) {

	Map<Character, char[]> map = new HashMap<Character, char[]>();
	map.put('f', new char[] { 'F', '4' });
	map.put('b', new char[] { 'B', '8' });
	String s = "fab";
	printStrings(s.toCharArray(), new StringBuilder(), map, 0);
    }

    public static void printStrings(char[] s, StringBuilder sb, Map<Character, char[]> map, int pos) {

	if (sb.length() == s.length) {
	    System.out.println(sb);
	    return;
	}
	char[] subs = map.get(s[pos]);
	sb.append(s[pos]);
	printStrings(s, sb, map, pos + 1);
	sb.setLength(sb.length() - 1);
	if (subs != null) {
	    for (int i = 0; i < subs.length; i++) {
		sb.append(subs[i]);
		printStrings(s, sb, map, pos + 1);
		sb.setLength(sb.length() - 1);
	    }
	}
    }