資訊專欄INFORMATION COLUMN
摘要：允許對(duì)非葉結(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，且允許對(duì)多個(gè)非葉節(jié)點(diǎn)進(jìn)行子節(jié)點(diǎn)的旋轉(zhuǎn)操作。將該操作生成的新字符串成為?，F(xiàn)在輸入兩個(gè)字符串，判斷該兩個(gè)字符串是否是。不僅要考慮數(shù)組的劃分，還要考慮所有可能的旋轉(zhuǎn)。
題目要求
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.
將一個(gè)字符串逐漸分解為一個(gè)葉節(jié)點(diǎn)為單個(gè)字母的樹。允許對(duì)非葉結(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，且允許對(duì)多個(gè)非葉節(jié)點(diǎn)進(jìn)行子節(jié)點(diǎn)的旋轉(zhuǎn)操作。將該操作生成的新字符串成為scrambled string。現(xiàn)在輸入兩個(gè)字符串，判斷該兩個(gè)字符串是否是scrambled string。
思路和代碼在一開始，我的思路出現(xiàn)了局限性，我希望通過列出所有的s1可以生成的scrambled string來判斷s2是否在該集合中。但是后序就會(huì)發(fā)現(xiàn)，如果要計(jì)算s1全部的scrambled string顯然是非常不明智的。不僅要考慮數(shù)組的劃分，還要考慮所有可能的旋轉(zhuǎn)。
之后，我就想到了利用遞歸來判斷二者究竟是不是互相旋轉(zhuǎn)生成的。我們先從一次旋轉(zhuǎn)來看，比如great和reatg，然后再進(jìn)行一次旋轉(zhuǎn)變成eratg。我們可以看到，reat和erat也是scrambled string。也就是說，我們只要找到合適的旋轉(zhuǎn)點(diǎn)，并判斷s1和s2在旋轉(zhuǎn)點(diǎn)左右的子字符串是否互為scrambled string就行。
遞歸的代碼非常簡(jiǎn)潔清晰。
public boolean isScramble(String s1, String s2) {
if(s1.equals(s2)) return true;
int[] alpha = new int[26];
for(int i = 0 ; i
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67616.html
摘要：首先將兩個(gè)字符串化成字符數(shù)組，排序后逐位比較，確定它們等長(zhǎng)且具有相同數(shù)量的相同字符。然后，從第一個(gè)字符開始向后遍歷，判斷和中以這個(gè)坐標(biāo)為中點(diǎn)的左右兩個(gè)子字符串是否滿足第一步中互為的條件設(shè)分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...
摘要：題目鏈接題目分析設(shè)計(jì)一個(gè)哈希類。需要有添加元素函數(shù)，判斷元素存在的函數(shù)，移除元素函數(shù)。思路這真的沒什么好說的了我把要存的值作為數(shù)組的鍵存儲(chǔ)。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 D87 705. Design HashSet 題目鏈接 705. Design HashSet 題目分析 設(shè)計(jì)一個(gè)哈希類。 需要有add添加元素函數(shù)，contains判斷元素存在的函數(shù)，remov...
摘要：位操作法復(fù)雜度時(shí)間空間思路我們?cè)O(shè)想，本來應(yīng)該的得到余，那么如果我們把忽略余數(shù)后分解一下，，也就是，也就是把商分解為，所以商的二進(jìn)制是。我們可以不斷的將乘的一次方，二次方，等等，直到找到最大那個(gè)次方，在這里是的四次方。 Divide Two Integers Divide two integers without using multiplication, division and m...
摘要：前端日?qǐng)?bào)精選未來布局之星更快地構(gòu)建使用預(yù)解析以及深入的虛擬原理原來與是這樣阻塞解析和渲染的怎樣把網(wǎng)站升級(jí)到中文視頻從談函數(shù)式與響應(yīng)式編程葉俊星系列三之煙花效果實(shí)現(xiàn)掘金的故事解剖表情動(dòng)圖的構(gòu)成設(shè)計(jì)系列傳統(tǒng)遞歸和尾調(diào)用的實(shí)現(xiàn)前端架構(gòu)經(jīng) 2017-09-24 前端日?qǐng)?bào) 精選 未來布局之星Grid更快地構(gòu)建DOM: 使用預(yù)解析, async, defer 以及 preload_JavaScri...
摘要：長(zhǎng)話短說，讓我們來看一道題統(tǒng)計(jì)的個(gè)數(shù)給定一個(gè)非負(fù)整數(shù)，對(duì)于任意，，計(jì)算的值對(duì)應(yīng)的二進(jìn)制數(shù)中的個(gè)數(shù)，將這些結(jié)果返回為一個(gè)數(shù)組。第二版本的時(shí)間復(fù)雜度是最后版本的時(shí)間復(fù)雜度是，是的二進(jìn)制數(shù)中的的個(gè)數(shù)，介于之間。 小胡子哥@Barret李靖給我推薦了一個(gè)寫算法刷題的地方leetcode.com，沒有ACM那么難，但題目很有趣。而且據(jù)說這些題目都來源于一些公司的面試題。好吧，解解別人公司的面試題...
閱讀 3709·2021-10-13 09:40
閱讀 3170·2021-10-09 09:53
閱讀 3570·2021-09-26 09:46
閱讀 1869·2021-09-08 09:36
閱讀 4262·2021-09-02 09:46
閱讀 1329·2019-08-30 15:54
閱讀 3197·2019-08-30 15:44
閱讀 1040·2019-08-30 11:06
