In java solution, I don’t understand the purpose of Set solved. And also I think the code doesn’t match the logic of the pics. Can anyone explain the logic of the code? Thanks
Hi Franklin,
The algorithm makes recursive calls inside an iterative loop. The solved Set is there for the purpose of implementing memoization. Memoization is the process of remembering which recursive call not to make. A recursive call is made on the second substring each time. But if the second string has already been solved, we can simply confirm its existence from the set without going into recursion.
As far as the illustration goes, do not think of the stack as the traditional stack data structure. This is the recursion stack. In the outer most loop when the first substring is found, we go one step deeper with a recursive call. This adds on to the recursive stack. The deeper we go by match more substrings, the higher our stack will be.
If a particular first substring matches but the second one does not, the programs will recursively move out back to the outer-most loop to find the first substring again. Moving back each recursive step removes a substring from the stack.
Hope this makes things clearer. Let us know if we can be of further assistance. Thank you for your feedback.
Regards,
Coderust.