牛客的标签里面有“动态规划”,搞得我一脸懵逼😳
本题应该用递归/贪心实现,条件如下:
- 基准1: 如果两个字符串长度不相等,返回false
- 基准2: 如果两个字符串相等,返回false
- 基准3: 如果两个字符串中对应字符的个数不相等,返回false
- 递归判断子字符串是否是乱序字符串
代码如下:
// // 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; } };