判断乱序字符串

牛客的标签里面有“动态规划”，搞得我一脸懵逼😳

本题应该用递归/贪心实现，条件如下：

1. 基准1: 如果两个字符串长度不相等，返回false
2. 基准2: 如果两个字符串相等，返回false
3. 基准3: 如果两个字符串中对应字符的个数不相等，返回false
4. 递归判断子字符串是否是乱序字符串

代码如下：

//
// Created by jt on 2020/8/30.
//
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    /**
     *
     * @param s1 string字符串
     * @param s2 string字符串
     * @return bool布尔型
     */
    bool isScramble(string s1, string s2) {
        // write code here
        return dfs(s1, s2);
    }

    bool dfs(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        unordered_map<char, int> um;
        for (int i = 0; i < s1.size(); ++i) {
            ++um[s1[i]]; --um[s2[i]];
        }
        for (auto it = um.begin(); it != um.end(); ++it) {
            if (it->second != 0) return false;
        }

        for (int i = 1; i < s1.size(); ++i) {
            if (dfs(s1.substr(0, i), s2.substr(0, i)) &&
                dfs(s1.substr(i), s2.substr(i))) return true;
            if (dfs(s1.substr(0, i), s2.substr(s1.size()-i)) &&
                    dfs(s1.substr(i), s2.substr(0, s1.size()-i))) return true;
        }
        return false;
    }
};