dfs二分周遊,采用字元直方統計進行一些裁剪。比如題目例子中的字元串:rgtae 和 great
當最頂層substring其中一個長度為一時的可能情況:
r | gtae <----> g | reat (最上層substring為旋轉)
r | gtae <----> grea | t (最上層substring已旋轉)
不管旋轉與否,兩個對應的字元,在一個字元區段内的字元直方統計總是相同的,如果不同必然不會是Scramble,此時我們就可以排除這個分支。
當枚舉到substring為2時
rg | tae <---> gr | eat
rg | tae <---> gre | at
可以發現子串rg的字元直方統計和gr是一緻的,tae和eat是一緻的是以這種劃分是一種可能,如果rg和gr是scramble 且
tae和eat也是scramble則整兩個字元串scramble
程式中為了友善起見隻進行了前一部分的字元直方統計,後一部分沒有進行(程式依然可以在後面的過程中對相應部分進行檢驗,正确性可以保證)
還可以将直方統計用的數組作為類的成員進而減少棧空間的使用