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.
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.
分治法
这道题的难度不大,但是题意理解起来比较难,最近几天木有写代码的状态 ,不多说了,明天把最后一道题解决掉,然后开始第二遍好好整理一下
代码看起来没啥难度:
public boolean isScramble(String s1,String s2){ if(s1.length() != s2.length()) return false; if(s1.length() <= 1 && s1.equals(s2)) return true; if(s1.length() == 2){ if(s1.equals(s2) ) return true; if(s1.charAt(0) == s2.charAt(1) && s1.charAt(1) == s2.charAt(0)) return true; return false; } char[] s1Array = s1.toCharArray(); char[] s2Array = s2.toCharArray(); Arrays.sort(s2Array); Arrays.sort(s1Array); for(int i = 0; i < s1.length(); i++){ if(s1Array[i] != s2Array[i]) return false; } boolean result = false; for(int i = 1; i < s1.length();i++){ String s1pre = s1.substring(0,i); String s1suf = s1.substring(i); String s2pre = s2.substring(0, i); String s2suf = s2.substring(i); result = isScramble(s1pre, s2pre) && isScramble(s1suf, s2suf); if(!result){ String s3pre = s2.substring(0, s1.length() - i); String s3suf = s2.substring(s1.length() - i); result = isScramble(s1pre, s3suf) && isScramble(s1suf, s3pre); } if(result) return true; } return result; }
相关推荐
python python_leetcode题解之087_Scramble_String
javascript js_leetcode题解之87-scramble-string.js
c语言基础 c语言_leetcode题解之0087_scramble_string.zip
在LeetCode平台上,字符串(String)专题是编程爱好者和求职者经常练习的重要部分。这个专题涵盖了字符串处理的各种算法问题,旨在提升编程者对字符串操作的熟练度和理解。在这个压缩包中,"LeetCode-String-master"很...
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 ...
java java_leetcode题解之Magical String.java
python python_leetcode题解之Binary String With Substrings Representing
c语言入门 c语言_leetcode题解perform-string-shifts.c
java java_leetcode题解之Flip String to Monotone Increasing.java
java java_leetcode题解之Construct String from Binary Tree.java
Reverse words in a string-leetcode
java java_leetcode题解之Permutation in String.java
vs code LeetCode 插件
java入门 java_leetcode题解之008_String_to_Integer(atoi)
《Python版LeetCode题解全集详解》 LeetCode是一个广受欢迎的在线编程挑战平台,致力于帮助程序员提升技能,特别是面试准备。这个压缩包“lc-all-solutions-master”包含了使用Python语言解决LeetCode所有问题的...
《使用leetcode-editor在IDE中进行LeetCode练习的全方位指南》 LeetCode是一个广受欢迎的在线编程练习平台,它提供了一系列的算法题目供程序员们提升技能。对于习惯在集成开发环境(IDE)中工作的开发者来说,将...
c语言入门 C语言_leetcode题解之08-string-to-integer-atoi.c
"IDEA leetcode-editor插件"就是将这两者结合的工具,允许用户在IDEA中直接进行LeetCode的编程挑战,无需离开开发环境,提高了刷题的便捷性。 该插件的主要功能包括: 1. **离线模式**:在无法访问LeetCode官网的...
js js_leetcode题解之8-string-to-integer-(atoi).js
Java的String类提供了丰富的API来处理字符串。 2. **链表**: - 链表题目通常涉及节点的插入、删除和遍历。Java中的LinkedList类提供了链表操作的基础,但解题时往往需要自定义节点类。 3. **栈与队列**: - 栈...