LeetCode 87文字列HERODINGのLeetCodeの道を乱す

以下に説明するアルゴリズムを使用して、文字列sを乱して文字列tを得ることができる.

          1 ，    
         > 1 ，      ：
                            。 ，        s ，              x   y ，    s = x + y 。
           「        」   「              」。 ，         ，s     s = x + y    s = y + x 。
      x   y               1          。

2つの長さが等しい文字列s 1とs 2を与えて、s 2がs 1の乱れ文字列であるかどうかを判断します.もしそうならtrueを返します.そうでなければfalseを返します.
例1:
入力:s 1=「great」、s 2=「rgeat」出力:true解釈:s 1で発生する可能性のある状況の1つは、「great」-->「gr/eat」//ランダムな下付きスケールで分割して2つのサブ文字列「gr/eat」-->「gr/eat」//ランダム決定:「この2つのサブ文字列の順序を維持する」「gr/eat」-->「g/r/e/at」//サブ文字列上でこのアルゴリズムを再帰的に実行することである.2つのサブ文字列はそれぞれランダムな下付き文字列で「g/r/e/at」-->「r/g/e/at」//ランダムに決定される:第1のグループは「2つのサブ文字列を交換する」、第2のグループは「この2つのサブ文字列の順序を維持する」「r/g/e/at」-->「r/g/e/a/t」//このアルゴリズムを継続的に再帰的に実行する.「at」を分割して「a/t」「r/g/e/a/t」-->「r/g/e/a/t」//ランダム決定:「この2つのサブ文字列の順序を一定に保つ」アルゴリズムが終了し、結果文字列はs 2と同様に「rgeat」であるs 1を乱してs 2を得る場合、s 2はs 1の乱雑文字列と考えられ、trueを返す
例2:
入力:s 1=「abcde」、s 2=「caebd」出力:false
例3:
入力:s 1=「a」、s 2=「a」出力:true
ヒント:

s1.length == s2.length
1 <= s1.length <= 30
s1   s2          

解題構想:これは難しい動的計画問題であり、コードの手順は複雑であり、参考問題の解を明らかにすることを提案し、コードは以下の通りである.

class Solution {
     
private:
    //             
    // -1    false，1    true，0      
    int memo[30][30][31];
    string s1, s2;

public:
    bool checkIfSimilar(int i1, int i2, int length) {
     
        unordered_map<int, int> freq;
        for (int i = i1; i < i1 + length; ++i) {
     
            ++freq[s1[i]];
        }
        for (int i = i2; i < i2 + length; ++i) {
     
            --freq[s2[i]];
        }
        if (any_of(freq.begin(), freq.end(), [](const auto& entry) {
     return entry.second != 0;})) {
     
            return false;
        }
        return true;
    }

    //         i1   ，        i2   ，       length，    
    bool dfs(int i1, int i2, int length) {
     
        if (memo[i1][i2][length]) {
     
            return memo[i1][i2][length] == 1;
        }

        //           
        if (s1.substr(i1, length) == s2.substr(i2, length)) {
     
            memo[i1][i2][length] = 1;
            return true;
        }

        //          c              
        if (!checkIfSimilar(i1, i2, length)) {
     
            memo[i1][i2][length] = -1;
            return false;
        }
        
        //       
        for (int i = 1; i < length; ++i) {
     
            //       
            if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
     
                memo[i1][i2][length] = 1;
                return true;
            }
            //      
            if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
     
                memo[i1][i2][length] = 1;
                return true;
            }
        }

        memo[i1][i2][length] = -1;
        return false;
    }

    bool isScramble(string s1, string s2) {
     
        memset(memo, 0, sizeof(memo));
        this->s1 = s1;
        this->s2 = s2;
        return dfs(0, 0, s1.size());
    }
};