首页 > 代码库 > 【leetcode】Scramble String
【leetcode】Scramble String
题目:给定两个串s1和s2,对s1串,我们可以将其分割成两部分,这两部分都不为空,而被分割成的两部分,又可以递归的进行分割,直到不能进行分割为止,也就是只有一个字符的时候,就不在分割了。问s2是否由s1的这种分割表示中,某步分割成的两部分交换得到的。这种交换可以在不同的分割点进行多次。
/* s1 |__________p____________| s1[0---p)---s1[0-p) 0 | len-1 s1[p-len)---s2[p-len) | s2 | |__________p____________| 0 len-1 s1 |__________p____________| 0 len - 1 s2 len-p s1[0---p)---s2[len-p, p) |__________|____________| s1[p-len)----s2[0,len - p) 0 |____________|len - 1 | p */ bool isScramble(string s1, string s2) { if(s1.size() == 0 && s2.size() == 0) return true; if(s1.size() != s2.size()) return false; //pruning string temp1 = s1; string temp2 = s2; sort(temp1.begin(),temp1.end()); sort(temp2.begin(),temp2.end()); if(temp1 != temp2) return false; int len = s1.size(); if(len == 1) return true; //try the every point for (int pt = 1; pt < len; ++pt) { if(isScramble(s1.substr(0, pt),s2.substr(0, pt)) && isScramble(s1.substr(pt, len - pt),s2.substr(pt, len - pt)) || isScramble(s1.substr(0, pt),s2.substr(len - pt, pt)) && isScramble(s1.substr(pt, len - pt),s2.substr(0, len - pt))) return true; } return false; }
居然在分割后,对左右部分的起始点弄不清了。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。