I am stuck on this interview question. Given a word S and an array of strings A. How to find all possible combinations of A elemnts that can form S. example :
S = "hotday"
A = ["o","ho","h","tday"]
the possible combinations are : ("h"+"o"+"tday") and ("ho"+"tday").
thanks
You can use backtracking. Here is some pseudo code:
def generateSolutions(unusedWords, usedWords, string, position):
if position == string.length():
print(usedWords)
else:
for word in unusedWords:
if word is a prefix of string[position ... s.length() - 1]:
generateSolutions(unusedWords - word, usedWords + word,
string, position + word.length())
generateSolution(words, an empty list, input string, 0)
The idea is very simple: we can just pick an unused word that matches a prefix of the rest of the input string and keep generating all valid combinations recursively(I assume that we can use each word from the given list of words only once). This solution has an exponential time complexity, but is not possible to do much better in the worst case. For instance, if the given string is abcdef...yz and the list of words is [a, b, c, ..., z, ab, cd, ..., yz], the number of such combinations is 2 ^ n / 2, where n is the length of the given string.
You could iterate through all permutations of A and see which ones fit. Python sample implementation:
import itertools
S = "hotday"
A = ["o","ho","h","tday"]
for count in range(len(A)):
for pieces in itertools.permutations(A, count):
if "".join(pieces) == S:
print pieces
Result:
('ho', 'tday')
('h', 'o', 'tday')
Yes, this is O(N!), but that's fine for the small A you've provided.
This is my java solution, it is the implementation of the pseudo code of "ILoveCoding" :
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
public class PossibleCombination {
public static void printPossibleCombinations(String[] tab, String S)
{
ArrayList<String> used = new ArrayList<String>();
ArrayList<String> notused = new ArrayList<String>(Arrays.asList(tab));
printPossibleCombinations(used, notused, S,0);
}
private static void printPossibleCombinations(ArrayList<String> used,
ArrayList<String> notused, String s,int pos) {
if (pos == s.length())
{ System.out.println("Possible combinaiton : ");
for(String e : used)
{
System.out.print(e + " - ");
System.out.println();
}
}
HashSet<String> prefixes = getPossiblePrefixes(s,pos);
for(String e : notused)
{
if (prefixes.contains(e))
{
ArrayList<String> isused = new ArrayList<String>(used);
isused.add(e);
ArrayList<String> isnotused = new ArrayList<String>(notused);
isnotused.remove(e);
printPossibleCombinations(isused, isnotused,s, pos + e.length());
}
}
}
private static HashSet<String> getPossiblePrefixes(String s, int pos) {
HashSet<String> prefixes = new HashSet<String>();
for(int i = pos ; i<= s.length() ; i++)
{
prefixes.add(s.substring(pos,i));
}
return prefixes;
}
public static void main(String[] args) {
String[] tab = {"o","ho","h","tday"};
String S = "hotday";
printPossibleCombinations(tab, S);
}
}