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.
Solution 1:
public boolean isScramble(String s1, String s2) { if(s1.equals(s2)) return true; // base case if(s1.length() != s2.length()) return false; int n = s1.length(); char[] s1Array = s1.toCharArray(); char[] s2Array = s2.toCharArray(); Arrays.sort(s2Array); Arrays.sort(s1Array); for(int i = 0; i < n; i++){ if(s1Array[i] != s2Array[i]) return false; } for(int i = 1; i < n;i++){ String s1pre = s1.substring(0,i); String s1suf = s1.substring(i); String s2pre = s2.substring(0, i); String s2suf = s2.substring(i); boolean result = isScramble(s1pre, s2pre) && isScramble(s1suf, s2suf); if(!result){ s2pre = s2.substring(0, s1.length() - i); s2suf = s2.substring(s1.length() - i); result = isScramble(s1pre, s2suf) && isScramble(s1suf, s2pre); } if(result) return true; } return false; }
Solution 2:
public boolean isScramble(String s1, String s2) { if(s1.equals(s2)) return true; // base case if(!isAnagram(s1, s2)) return false; int n = s1.length(); for(int i = 1; i < n;i++){ String s1pre = s1.substring(0,i); String s1suf = s1.substring(i); String s2pre = s2.substring(0, i); String s2suf = s2.substring(i); boolean result = isScramble(s1pre, s2pre) && isScramble(s1suf, s2suf); if(!result){ s2pre = s2.substring(0, s1.length() - i); s2suf = s2.substring(s1.length() - i); result = isScramble(s1pre, s2suf) && isScramble(s1suf, s2pre); } if(result) return true; } return false; } private boolean isAnagram(String s1, String s2) { if(s1.length() != s2.length()) return false; int[] table = new int[256]; int n = s1.length(); for(int i=0; i<n; i++) { table[s1.charAt(i)]++; } for(int i=0; i<n; i++) { char c = s2.charAt(i); if(--table[c] < 0) return false; } return true; }
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案 LeetCode-String #这是LeetCode里面String专题中的python版答案
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答