[leetcode]Scramble String

本文主要是介绍[leetcode]Scramble String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3D dp问题

class Solution {
public:bool isScramble(string s1, string s2) {// Start typing your C/C++ solution below// DO NOT write int main() functionint N = s1.size();if(N != s2.size()) return false;if(N == 0) return s1 == s2;vector<vector<vector<bool>>> f(N, vector<vector<bool>>(N, vector<bool>(N+1, false)));for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){f[i][j][1] = (s1[i] == s2[j]);}}bool tmp;for(int len = 2; len <= N; len++){for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){for(int k = 1; k < len; k++){if(i+k >= N || j+k >= N || j+len-k >= N) continue;tmp = f[i][j][k] && f[i+k][j+k][len-k] || f[i][j+len-k][k] && f[i+k][j][len-k];if(tmp){f[i][j][len] = true;break;}   }}}}return f[0][0][N];}
};

这篇关于[leetcode]Scramble String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---