Scramble String
Given a strings1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation ofs1="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 stringss1ands2of the same length, determine ifs2is a scrambled string ofs1.
好困难的一题,自己研究出来了,不过很难确定是什么判断条件结束,所以耽误了不少时间。
一看样子就知道使用递归无疑了。
主要卡我时间最长的是递归的时候需要交叉递归的,因为根的两个子树以及下面的所有子树都是可以调换的。
思路:
1 检查长度是否一样,不一样就返回false
2 检查当前两个字符是否为乱序,但是所有字符数相等,检查有两个方法: 1) 使用hash表 2)操作字符string排序比较;这里计算就相当于剪枝了,没有这一步会超时的。
3 逐个字符分隔成两个子树,然后递归,注意s1和s2是可以交叉递归的。
好像字符串和一般原始数据一样快,直接操作字符串string的速度很快,比如本题的直接操作字符串的速度也很快。
不过注意如果使用fixedTable为256,即假设为256个ascII码,那么就会比假设为26个小写字符的速度慢上一倍。所以要搞清楚题目要求,根据题目设置hash表
本题也可以使用三维动态规划法,leetcode上有几个列子都是使用动态规划法的。
LeetCode上的例子一般都很好,但是这次例外了,这些动态规划法的例子并不好,因为本题使用动态规划法增加了空间复杂度,甚至时间复杂度,而且实际运行时间比递归剪枝法慢。
下面是使用hash表,利用四点定位递归的程序。
vector<int> fixedTable;
vector<int> countTable;
bool isScramble2(string s1, string s2)
{
if (s1.length() != s2.length()) return false;
return scrambleRecur(s1,s2,0,s1.length()-1,0,s2.length()-1);
}
bool scrambleRecur(string &s1, string &s2,
int begin1, int back1, int begin2, int back2)
{
if (begin1 > back1 || (begin1==back1 && s1[begin1]==s2[begin2]))
return true;
fixedTable.clear(); fixedTable.resize(26);
countTable.clear(); countTable.resize(26);
//有重复的时候需要特殊处理
for (int i = begin1; i <= back1; i++) //例如:"abab", "bbaa"
{
fixedTable[s1[i]-'a']++;
}
for (int i = begin2; i <= back2; i++)
{
countTable[s2[i]-'a']++;
if (fixedTable[s2[i]-'a'] < countTable[s2[i]-'a']) return false;
}
//注意:不要写成i<=back-begin,因为递归最重要的原则:子递归必定要比原问题要小,否则就会无限递归,内存溢出了。
for (int i = 0; i < back1-begin1; i++)
{
if (scrambleRecur(s1,s2,begin1,begin1+i,begin2, begin2+i)
&&scrambleRecur(s1,s2,begin1+i+1,back1,begin2+i+1,back2)
||scrambleRecur(s1,s2,begin1,begin1+i, back2-i,back2)
&&scrambleRecur(s1,s2,begin1+i+1,back1,begin2,back2-i-1))
return true;
}
return false;
}
//2014-2-14 update
bool isScramble(string s1, string s2)
{
if (s1.length() != s2.length()) return false;
if (s1 == s2) return true;
int A[26] = {0};
for(auto x:s1)
A[x-'a']++;
for(auto x:s2)
A[x-'a']--;
for(auto x:A)
if(x != 0) return false;
if (s1.length() < 4) return true;
for (int i = 1; i < s1.length(); i++)
{
if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
isScramble(s1.substr(i), s2.substr(i))
|| isScramble(s1.substr(0, i), s2.substr(s2.length()-i)) &&
isScramble(s1.substr(i), s2.substr(0,s2.length()-i)))
return true;
}
return false;//注意:别忘了最后返回
}
分享到:
相关推荐
leetcode 答案 LeetCode-String #这是LeetCode里面String专题中的python版答案
c++ c++_c++编程基础之leetcode题解第43题字符串相乘
c++ c++_c++编程基础之leetcode题解第8题字符串转换整数
c语言 c语言_c语言编程基础之leetcode题解第8题字符串转整数
题目来源:https://leetcode-cn.com/problems/compress-string-lcci 题目 字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的...
给定一个字符串和一个整数 k,你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符,则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符,则反转前 k 个字符,并将剩余...
参考了评论区 Felix8bit 的答案解题思路:先根据每个词出现的概率进行统计,再把统计的词按照按照次数从大到小放入新字符串中代码中实现了 Comparato
代码:public boolean buddyStrings(String s, String goal) {* 时间复杂度:令 $n$ 为两字符串之间的最大长
将两者相应字符的映射关系都记录下来,比如那么假定两个映射关系m1/m2分别指s->t和t->s映射:所以遍历所有的字符 ,对当前的字符1、如果m1中无映射关系,
简介:如果交换字符串X中的两个不同位置的字母,使得它和字符串Y相等,那么称X和Y两个字符串相似。如果这两个字符串本身是相等的,那它们也是相似的。给你一个字符串列
leetcode思维导图-字符串
找到X后移3位解题思路每次找到一个'X'都可以一下子使得连续的至少三个字母变成'O'所以遍历字符串的时候,发现'X',就计为一次转换,并且将当前指针后移3位发现
Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input ...
1055.Shortest_Way_to_Form_String_形成字符串的最短路径【LeetCode单题讲解系列】
344.Reverse_String反转字符串【LeetCode单题讲解系列】
Leetcode 451. 根据字符出现频率排序问题描述451. 根据字符出现频率排序 - 力扣(LeetCode)算法解法1: 计数排序def frequen
LeetCode 205的题目是“同构字符串”(Isomorphic Strings),要求判断两个字符串是否是同构的。如果字符串s可以通过字符替换得到字符串t,那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换,同时...
python python_leetcode面试题解之无重复字符的最长子串
leetcode字符串转换为整数
不会394.-解码字符串-c-Leetcode 给定一个编码字符串,返回它的解码字符串。 编码规则是:k[encoded_string],其中方括号内的encoded_string 正好重复k 次。 请注意,k 保证为正整数。 您可以假设输入字符串始终有效...