What is the best solution?

#1

I have generated the combinations possible but how do i search for them in the given array?

#2

@tusharnitharwal,

Different approaches:

  1. A simple brute force iteration, for each generated combination, check with each given string.
  2. Recursion, to reduce no. of redundant matchings and also no need of generating all the combinations (cause there could be many, at least 3^10 in worst case)
  3. The unchallenged, KMP algorithm, (leave it for now). --“The best solution”

You should try doing this with recursion for now, will help you think recursively, just think to what should you change a given digit to (one of the three or four alphabets it represents eg 2 -> {‘a’,‘b’,‘c’}), and recursively call for the next digit in str.

#3

can you please elaborate on the recursive solution

#4

@tusharnitharwal,
Never mind the above recursive approach, I was trying to merge both the generation of combination and matching of these to strings in a single recursion. That would be quite complicated, rather just do this:

Generate all combinations using recursion (I think you said you have already done it), now just check by iterative brute force, i.e try to match all combination with all strings, and print the one which give a match.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.