題目描述

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.

思路：1、對(duì)于該問(wèn)題，首先明白是在判斷字符串S2是否為S1的scrambled string，分情況討論的話，可以剛開(kāi)始先看是否equals，這樣可以判斷長(zhǎng)度為一的字符串；

2、接下來(lái)可以判斷字符串的長(zhǎng)度是否相同；

3、之后判斷是否出現(xiàn)的字符相同，這里新建了一個(gè)長(zhǎng)度為26的數(shù)組，要習(xí)慣這種思路，在前面的題中，找出現(xiàn)次數(shù)為n的數(shù)組中只是出現(xiàn)一次的數(shù)字也將32位的值分別存在了長(zhǎng)度為32的數(shù)組里；

4、對(duì)遞歸的使用，分兩種，一種是沒(méi)有進(jìn)行左右轉(zhuǎn)換，一種是進(jìn)行了左右轉(zhuǎn)換；

public class Solution {public boolean isScramble(String s1, String s2) {if (s1.equals(s2))return true;int[] letters = new int[26];for (int i = 0; i < s1.length(); i++) {letters[s1.charAt(i) - 'a']++;letters[s2.charAt(i) - 'a']--;}for (int i = 0; i < 26; i++)if (letters[i] != 0)return false;for (int i = 1; i < s1.length(); i++) {//當(dāng)前分割出沒(méi)有交換if (isScramble(s1.substring(0, i), s2.substring(0, i))&& isScramble(s1.substring(i), s2.substring(i))) //因?yàn)樵摵瘮?shù)是返回值為布爾型的，所以可以把其放在條件里面return true;//當(dāng)前分割出交換---左右交換,這兩段可以合在一起，但是可讀性比較差if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i))&& isScramble(s1.substring(i), s2.substring(0, s2.length() - i)))return true;}return false;

總結(jié)

以上是生活随笔為你收集整理的LeetCode: scramble-string的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。