天天看點

LeetCode Scramble String

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

程式中為了友善起見隻進行了前一部分的字元直方統計,後一部分沒有進行(程式依然可以在後面的過程中對相應部分進行檢驗,正确性可以保證)

還可以将直方統計用的數組作為類的成員進而減少棧空間的使用