leetcode87. Scramble String

BlackFlagBin 發布于2019-08-15 11:13 / 2461人閱讀

摘要：允許對非葉結點的兩個子節點進行旋轉，且允許對多個非葉節點進行子節點的旋轉操作。將該操作生成的新字符串成為。現在輸入兩個字符串，判斷該兩個字符串是否是。不僅要考慮數組的劃分，還要考慮所有可能的旋轉。

題目要求

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.

將一個字符串逐漸分解為一個葉節點為單個字母的樹。允許對非葉結點的兩個子節點進行旋轉，且允許對多個非葉節點進行子節點的旋轉操作。將該操作生成的新字符串成為scrambled string。現在輸入兩個字符串，判斷該兩個字符串是否是scrambled string。

思路和代碼

在一開始，我的思路出現了局限性，我希望通過列出所有的s1可以生成的scrambled string來判斷s2是否在該集合中。但是后序就會發現，如果要計算s1全部的scrambled string顯然是非常不明智的。不僅要考慮數組的劃分，還要考慮所有可能的旋轉。
之后，我就想到了利用遞歸來判斷二者究竟是不是互相旋轉生成的。我們先從一次旋轉來看，比如great和reatg，然后再進行一次旋轉變成eratg。我們可以看到，reat和erat也是scrambled string。也就是說，我們只要找到合適的旋轉點，并判斷s1和s2在旋轉點左右的子字符串是否互為scrambled string就行。

遞歸的代碼非常簡潔清晰。

    public boolean isScramble(String s1, String s2) {
        if(s1.equals(s2)) return true;
        int[] alpha = new int[26];
        for(int i = 0 ; i

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 LeetCode_String Scramble Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67616.html

[LintCode/LeetCode] Scramble String

摘要：首先將兩個字符串化成字符數組，排序后逐位比較，確定它們等長且具有相同數量的相同字符。然后，從第一個字符開始向后遍歷，判斷和中以這個坐標為中點的左右兩個子字符串是否滿足第一步中互為的條件設分為和，分為和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 評論0 收藏0
Leetcode PHP題解--D87 705. Design HashSet

摘要：題目鏈接題目分析設計一個哈希類。需要有添加元素函數，判斷元素存在的函數，移除元素函數。思路這真的沒什么好說的了我把要存的值作為數組的鍵存儲。最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 D87 705. Design HashSet 題目鏈接 705. Design HashSet 題目分析設計一個哈希類。需要有add添加元素函數，contains判斷元素存在的函數，remov...

why_rookie 2019-07-01 14:00 評論0 收藏0
[Leetcode] Divide Two Integers 整數整除

摘要：位操作法復雜度時間空間思路我們設想，本來應該的得到余，那么如果我們把忽略余數后分解一下，，也就是，也就是把商分解為，所以商的二進制是。我們可以不斷的將乘的一次方，二次方，等等，直到找到最大那個次方，在這里是的四次方。 Divide Two Integers Divide two integers without using multiplication, division and m...

張春雷 2019-08-14 12:46 評論0 收藏0
2017-09-24 前端日報

摘要：前端日報精選未來布局之星更快地構建使用預解析以及深入的虛擬原理原來與是這樣阻塞解析和渲染的怎樣把網站升級到中文視頻從談函數式與響應式編程葉俊星系列三之煙花效果實現掘金的故事解剖表情動圖的構成設計系列傳統遞歸和尾調用的實現前端架構經 2017-09-24 前端日報精選未來布局之星Grid更快地構建DOM: 使用預解析, async, defer 以及 preload_JavaScri...

yuanzhanghu 2019-08-21 16:43 評論0 收藏0
別人家的面試題：統計“1”的個數

摘要：長話短說，讓我們來看一道題統計的個數給定一個非負整數，對于任意，，計算的值對應的二進制數中的個數，將這些結果返回為一個數組。第二版本的時間復雜度是最后版本的時間復雜度是，是的二進制數中的的個數，介于之間。小胡子哥@Barret李靖給我推薦了一個寫算法刷題的地方leetcode.com，沒有ACM那么難，但題目很有趣。而且據說這些題目都來源于一些公司的面試題。好吧，解解別人公司的面試題...

SQC 2019-08-19 18:27 評論0 收藏0