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; }
相关推荐
leetcode 答案 LeetCode-String #这是LeetCode里面String专题中的python版答案
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 ...
leetcode字符串转换为整数
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Reverse words in a string-leetcode
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode中文版
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 双指针 编号 题目 LeetCode 11 Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 ...
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode 刷题笔记