注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex87 Scramble String  

2015-05-29 23:15:29|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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再划分成两段,然后判定他们的顺序和逆序是否是sramble string,递归和动态规划的过程都是这样。
第一种递归

class Solution {
public:
bool isScramble(string s1, string s2) {

bool result;
result =
recursive(s1, s2);
return result;
}
//递归的方法的思路就比较简单了
//毫无悬念地超时了,时间复杂读貌似是3^n
bool recursive(string s1, string s2)
{
/*
* 把s1从下标 i分开, 前半部分是 0~i 后半部分是i ~len-i
* 所以有两种情况 s11 0~i s21 0~i 并且 s12 s22 scramble
* 或者 s11 s22 并且 s12 s21 scramble
*/
if (s1.size() != s2.size()) return false;
if (s1 == s2) return true;

string tmp1 = s1;
string tmp2 = s2;
sort(tmp1.begin(),tmp1.end()); //对于scramble必须满足s1和s2排序后相等
sort(tmp2.begin(), tmp2.end());

if (tmp1 != tmp2) //加了排序比较后居然就过了
return false;
for (int isep = 1; isep < s1.size(); ++isep)
{
//seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
string seg11 = s1.substr(0, isep);
string seg12 = s1.substr(isep);

//see if forward order is ok
string seg21 = s2.substr(0, isep);
string seg22 = s2.substr(isep);
if (isScramble(seg11, seg21) && isScramble(seg12, seg22))
return true;

//see if reverse order is ok
seg21 = s2.substr(s2.size() - isep); //往后的长度为isep那部分
seg22 = s2.substr(0, s2.size() - isep); //
if (isScramble(seg11, seg21) && isScramble(seg12, seg22)) return true;

}
return false;
}
};


第二种 动态规划
开一个三维数组
dp[k][i][j],i表示s1的起点,j表示s2的起点,k表示,他们i,j下标后面各跟上k个字符是否sramble string。这个过程中减少了很多重复的计算。

class Solution {
public:
bool isScramble(string s1, string s2) {

bool result;
result = traverse(s1, s2);
return result;
}

bool traverse(string s1, string s2)
{
//动态规划也是一样的 开一个数组 dp[k][i][j]
//第二维 i表示s1的起点是i,第三维j表示 s2的起点
//第二维度表示后面k个是scramble的
int len = s1.size();
vector<vector<bool>>tmp(len, vector<bool>(len,false));
vector<vector<vector<bool>>> dp(len,tmp);
int i, j, k;
for (i = 0; i < len; i++)
for (j = 0; j < len; j++)
dp[0][i][j] = (s1[i]==s2[j]); //如果相等的话他们自动scramble了
for (k = 2; k <= len; k++)
{
//循环后面的长度
for (i = len - k; i >= 0; i--)
{
for (j = len - k; j >= 0; j--)
{
bool res = false;
for (int m = 1; m < k&&!res; m++)
{
//只要r有一次为true的,那么就是true直接退出了
//下面也是将字符分成两部分,m就是前半部分的个数
bool part1 = dp[m - 1][i][j] && dp[k - m - 1][i + m][j+m];
// i,j后面 m-1匹配 并且i+m 后面k-m-1个 与 j+m后面k-m-1个匹配
bool part2 = dp[m - 1][i][j + k - m] && dp[k - m - 1][i + m][j];
// i,j+k-m后面 m-1匹配 并且i+m 后面k-m-1个 与 j后面k-m-1个匹配

//这一部分和递归是一样的
res = part1 || part2;
}
dp[k-1][i][j] = res; //这个地方的第一维度下标应该 -1
}
}
}
return dp[len - 1][0][0];

}
};



参考
http://blog.csdn.net/doc_sgl/article/details/12401335
http://blog.unieagle.net/2012/10/23/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Ascramble-string%EF%BC%8C%E4%B8%89%E7%BB%B4%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/
http://www.cnblogs.com/easonliu/p/3696135.html
http://blog.sina.com.cn/s/blog_b9285de20101gy6n.html
  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017