首页 > 代码库 > 【leetcode】 Scramble String (hard)★
【leetcode】 Scramble String (hard)★
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great / gr eat / \ / g r e at / a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat / rg eat / \ / r g e at / a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae / rg tae / \ / r g ta e / t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
判断两个字符串s1和s2是否可以通过旋转实现。
思路：开始傻眼了，反应不过来。第二天恍然大悟，用递归，分左右部分，变成子问题。但是最开始我以为划分树只有一种方式，后来发现树可以随意的划分，左子树可以有任意个字符，右子树也是。所以需要循环遍历所有条件。再然后是可能s1的左半部分在s2中位于左半部分 或者是右半部分，所以对这两种情况也要都考虑到。
循环的时候用了截枝，如果两边的字符有不一致的直接跳过该次循环。
#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <stack>#include <string>using namespace std;class Solution {public: bool isScramble(string s1, string s2) { if(s1.length() != s2.length()) return false; if(s1 == s2) return true; if(!isEqual(s1 , s2)) { return false; } for(int i = 1; i < s1.length(); i++) { int leftlength = i; int rightlength = s1.length() - leftlength; string s1left1 = s1.substr(0, leftlength); string s2left1 = s2.substr(0, leftlength); string s1right1 = s1.substr(leftlength, rightlength); string s2right1 = s2.substr(leftlength, rightlength); string s1left2 = s1.substr(rightlength, leftlength); string s1right2 = s1.substr(0, rightlength); if(!isEqual(s1left1,s2left1) && !isEqual(s1left2,s2left1)) { continue; } if((isScramble(s1left1, s2left1) && isScramble(s1right1, s2right1)) || (isScramble(s1left2, s2left1) && isScramble(s1right2, s2right1))) { return true; } } return false; } //判断两个字符串的字母组成是否一致 bool isEqual(string s1, string s2) { if(s1.length() != s2.length()) return false; for(int i = 0; i < s1.length(); i++) { int locate = s2.find(s1[i]); if(locate == string::npos) { return false; } else { s2.erase(s2.begin() + locate); } } return true; }};int main(){ Solution s; string s1 = "oatzzffqpnwcxhejzjsnpmkmzngneo"; string s2 = "acegneonzmkmpnsjzjhxwnpqffzzto"; //string s1 = "gneo"; //string s2 = "gneo"; bool ans = s.isScramble(s1, s2); return 0;}
有大神给出了正宗动态规划的解法，非常精简，要好好学习。 不过这个方法算了所有的情况所以时间比我的要长，差不多150ms, 我的是50ms左右。
dp[i][j][l] means whether s2.substr(j,l) is a scrambled string of s1.substr(i,l) or not.
class Solution {public: bool isScramble(string s1, string s2) { int len=s1.size(); bool dp[100][100][100]={false}; for (int i=len-1;i>=0;i--) for (int j=len-1;j>=0;j--) { dp[i][j][1]=(s1[i]==s2[j]); for (int l=2;i+l<=len && j+l<=len;l++) { for (int n=1;n<l;n++) { //所有划分左右区间的情况 dp[i][j][l]|=dp[i][j][n]&&dp[i+n][j+n][l-n]; //s1的左边对s2的左边 dp[i][j][l]|=dp[i][j+l-n][n]&&dp[i+n][j][l-n];//s1的左边对s2的右边 } } } return dp[0][0][len]; }};
【leetcode】 Scramble String (hard)★