Please provide me with the recurrsive tree for this problem.
Do we need to use any data structures like hash maps or something for this problem?
Mapped Strings.... Recursive tree
First we need to do the recursive formulation of the problem.
lets say original input is x and f(x) is solution of the problem. then we can write f(x) recursively as:
f(x) = {code of first digit + f(x[1:]),
code of first 2 digits + f(x[2:]) if first 2 digits<=26
}
here x[r:] means remaining part of x leaving first r digits.
lets see one example of this formulation:
say x = 123
step1: f(123) ={ code of 1 + f(23), code of 12 + f(3) }
= {“A” + f(23), “L” + f(3)}
step2: f(23) = {code of 2 + f(3), code of 23 + f(nothing)}
= {“B” + f(3) , “W” + f(nothing)}
step3: f(3) = {code of 3 + f(nothing)} = {“C” + f(nothing)} = {“C”}
step4: f(nothing) = “” …this is your base condition of recursion.
put all computed things in step1:
f(123) = {“A” + {“BC” , “W”}, “L”+“C”}
= {“ABC” , “AW”, “LC”}
here + is concatenation of string.
you need to convert this mathematical expression into java code, which should be pretty straightforward.
as you can see, the function returns a list of strings, so you need ArrayList as a data structure. and a mapping data structure which can map 1-A,2-B…so on. for this mapping you can use HashMap, but simple array can also be used with 1,2,3,…26 as index values.
Thanks