Google scramble string (III)

Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg”
tiger
/    \
ti    ger
/  \   /   \
t    i  g    er
/  \
e    r

itreg
/    \
it     reg
/  \   /   \
t    i  g    re
/  \
e    r

In above case, since s1 can be generated from str2, that is, str1 can be generated from the partition tree, which has the same leaf of str2, but the order of its child can be switched. So str1 is said to be a scramble string of str2.

A counter example is that Tiger and Tgrie are not scramble string of each other

Question: Given two strings str1 and str2, are they scramble string of each other?

A approach is provided in my previous blog Google Scramble String (I): Without Duplicated characters, however, such approach can only handle the case when there are no duplicated characters in string.

What about the case when a string contains duplicated characters?

Example: A: aabbbaccd,  B: aabcdbcba, are them scramble strings of each other?

It is proposed in this paper a recursive-based Divide-And-Conquer approach, this approach is more efficient than my preivous approaches.

The principle of this approach goes as following
1) Given two strings A and B, try to split each of them into two sub-strings sA1,sA2,sB1, sB2 where sA1 and sB1 are anagrams and sA2 and sB2 are anagrams.
2) If sA1 and sB1 are the scramble strings while sA2 and sBs are scramble strings, then A and B should be scramble strings.
3) Recursivly analyze sA1 and sB1, sA2 and sB2 by start over from step 1).

In previous example

str1 = aabbbaccd, str2: aabcdbcba,

They are split as: (aab)(bbaccd),  (aab)(cdbcba) => compare bbaccd and cdbcba
They are split as: (bbac)(cd),  (cd)(bcba) => compare bbac and bcba
They are split as: (b)(bac), b(cba) => (ba)(c) vs (c)(ba)

They are scramble stromh of each other

// index means how many characters in a new anagram
// direction means the way of split
//example, abcdef and efcabd, then direction = false and index = 2 for "ef"
//example, abcdef and abefcd, then direction = true and index =1 for "a"
public static List<int> stringSplitIndex(char[] chArr1, char[] chArr2, int start1, int end1, int start2, int end2, List<int> indexList, List<bool> directionList)
        {
            int index = 0;
            //two ways of anagram, AB-AB and AB-BA
            Dictionary<char, int>
                headToHeadDict = new Dictionary<char, int>(),
                headToTailDict = new Dictionary<char, int>(); 
            while (start1+index<end1)
            {
                //add value from first string
                if (!headToHeadDict.ContainsKey(chArr1[start1 + index]))
                    headToHeadDict.Add(chArr1[start1 + index], 1);
                else
                {
                    headToHeadDict[chArr1[start1 + index]]++;
                    if(headToHeadDict[chArr1[start1 + index]]==0)
                        headToHeadDict.Remove(chArr1[start1 + index]);
                }
                if (!headToTailDict.ContainsKey(chArr1[start1 + index]))
                    headToTailDict.Add(chArr1[start1 + index], 1);
                else
                {
                    headToTailDict[chArr1[start1 + index]]++;
                    if(headToTailDict[chArr1[start1 + index]]==0)
                        headToTailDict.Remove(chArr1[start1 + index]);
                }
                //delete value from dictionary by the second string
                if (!headToHeadDict.ContainsKey(chArr2[start2 + index]))
                    headToHeadDict.Add(chArr2[start2 + index], -1);
                else
                {
                    headToHeadDict[chArr2[start2 + index]]--;
                    if (headToHeadDict[chArr2[start2 + index]] == 0)
                        headToHeadDict.Remove(chArr2[start2 + index]);
                }
                if (!headToTailDict.ContainsKey(chArr2[end2-index]))
                    headToTailDict.Add(chArr2[end2-index], -1);
                else
                {
                    headToTailDict[chArr2[end2 - index]]--;
                    if (headToTailDict[chArr2[end2 - index]] == 0)
                        headToTailDict.Remove(chArr2[end2 - index]);
                }
                //at this point the strings can be split into two anagrams
                if (headToHeadDict.Count == 0)
                {
                    indexList.Add(index);
                    directionList.Add(true);
                }
                if (headToTailDict.Count == 0)
                {
                    indexList.Add(index);
                    directionList.Add(false);
                }
                index++;
            }

            return indexList;
        }
        public static Boolean googleScrambleStringRecursive(char[] ch1, char[] ch2, int start1, int end1, int start2, int end2)
        {
            if (end1 == start1 && end2 == start2 && ch1[start1] == ch2[start2])
                return true;
            if(end1-start1!=end2-start2)
                return false;
            List<bool> directionList = new List<bool>();
            List<int> indexList = stringSplitIndex(ch1, ch2, start1, end1, start2, end2, new List<int>(),directionList);
            if (indexList.Count==0)
                return false;
            bool isScramble = false;
            for(int i=0;i<directionList.Count;i++)
            {
                if(directionList[i])
                {
                    isScramble =  googleScrambleStringRecursive(ch1, ch2, start1, start1+indexList[i], start2, start2+indexList[i]) &&
                           googleScrambleStringRecursive(ch1, ch2, start1 + indexList[i] + 1, end1, start2 + indexList[i] + 1, end2); 
                    if(isScramble)
                        return isScramble;
                }
                else
                {
                    isScramble = googleScrambleStringRecursive(ch1, ch2, start1, start1 + indexList[i], end2 - indexList[i], end2) &&
                           googleScrambleStringRecursive(ch1, ch2, start1 + indexList[i] + 1, end1, start2, end1 - indexList[i] - 1);
                    if(isScramble)
                        return isScramble;
                }
            }
            return isScramble;
        }