[Leetcode Solution] Scramble String

Analysis

• With the same basic idea there are some slight different implementations in details. 

• Essence is recursion.Let f(s1,s2) denote if s2 is a scrambled string of s1. Then 
• f(s1,s2)==True iff there is a number i that 
• f(s1[1..i], s2[1..i])==True
• or f(s1[1..i], s2[n-i..n])==True

• There are some different implementation in major part like dynamic programming, momeriziation search and recursive search.
• And there are some details slight differences.
• When doing the search, in the recursion function signature, each time create the new sub-string and passing string itself, or using two indices to denote the start and end position and pass the original string reference. This strategy can reduce half of the running time
• Before recursively check the sub-string, first pre valid if it is possible that two string are scrambled string by counting the number of each element appeared in both of the string.This can be done by two means
• Sort and then compare
• Hash and compare
• First method reduce 20% time
• Compared with memoriziation search, directly recursive search reduced the searching time which is beyond my expectation

Note

• if using memorization, may not passing the hash table as parameter each time, instead, could use a static variable in function

Code

UPDATED AT LEETCODE 2ND PASS