LeetCode Online Judge 题目C# 练习 - Scramble String

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         public static bool ScrambleString(string s1, string s2)
 2         {
 3             if (s1 == s2)
 4                 return true;
 5             else if (s1.Length != s2.Length)
 6                 return false;
 7             else if (s1.Length == 1 && s1 != s2)
 8                 return false;
 9             else
10             {
11                 for (int i = 1; i < s1.Length; i++)
12                 {
13                     if ((ScrambleString(s1.Substring(0, i), s2.Substring(0, i)) && ScrambleString(s1.Substring(i), s2.Substring(i))) ||
14                         ScrambleString(s1.Substring(0, i), s2.Substring(s2.Length - i)) && ScrambleString(s1.Substring(i), s2.Substring(0, s2.Length - i)))
15                     {
16                         return true;
17                     }
18                 }
19                 return false;
20             }
21         }

代码分析：

　　递归，看来有关树的题，用递归还是八九不离十了。

　　这段code过不了在LeetCdoe的Large Case。改成下面这样才可以。 其实时间复杂度一样

 1         public static bool ScrambleStringOpt(string s1, string s2)
 2         {
 3             if (s1 == s2)
 4                 return true;
 5             else if (s1.Length != s2.Length)
 6                 return false;
 7             else if (s1.Length == 1 && s1 != s2)
 8                 return false;
 9             else
10             {
11                 int n = s1.Length;
12                 for (int i = 1; i <= n / 2; i++)
13                 {
14                     string a1 = s1.Substring(0, i), b1 = s1.Substring(i), a2 = s2.Substring(0, i), b2 = s2.Substring(i);
15                     string c1 = s1.Substring(0, n - i), d1 = s1.Substring(n - i), c2 = s2.Substring(0, n - i), d2 = s2.Substring(n - i);
16 
17                     if (ScrambleStringOpt(a1, a2) && ScrambleStringOpt(b1, b2))
18                         return true;
19                     if (ScrambleStringOpt(a1, d2) && ScrambleStringOpt(b1, c2))
20                         return true;
21                     if (ScrambleStringOpt(d1, a2) && ScrambleString(c1, b2))
22                         return true;
23                     if (ScrambleStringOpt(d1, d2) && ScrambleString(c1, c2))
24                         return true;
25                 }
26                 return false;
27             }
28         }

代码分析：

　　要提升效率， && 操作符，把做得快的放在前面！如果把做的慢的放前面的话，LeetCode Large Case 过不了。。。