Correct me if I am wrong XD. I am just trying to give a thought. Lets say length of pattern is P and length of string is S. Only to study the worst case where each character of pattern will be different, we always choose the loop part to execute. For each recursion level, there will be a possibly O(S) loop and inside that loop, there will be another possibly O(S) to create the substring and a recursive call at each iteration. (Noted here, every new string's hash value will not be calculated and cached until its hashCode() being called. so set.add(substring) will cost another O(S) to hash the string. Since it is at the same level with substring creation, so we can combine both operation as run time O(S))
Recursion depth will be bounded by O(P).
Run time complexity can be written as
O(S*(S+ S*(S + S*(.....S*(S) ) ) ) ) => O(S^(P+1) + S^(P)+S^(P-1)+...S^2) = O(S^(P+1))
Word Pattern II