LeetCode/087-scramble-string/scramble-string.js at master · theFool32/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// 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.
//
// Example 1:
//
//
// Input: s1 = "great", s2 = "rgeat"
// Output: true
//
//
// Example 2:
//
//
// Input: s1 = "abcde", s2 = "caebd"
// Output: false
//


/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */

var isScramble = function(s1, s2) {
  if (s1 === s2) {
    return true
  }
  if (s1.length != s2.length) {
    return false
  }
  if (s1.split('').sort().join('') !== s2.split('').sort().join('')) {
    return false
  }
  for (var i = 1;i < s1.length;++i) {
    if ((isScramble(s1.substr(0, i), s2.substr(0,i)) &&
         isScramble(s1.substr(i), s2.substr(i))) ||
        (isScramble(s1.substr(0, i), s2.substr(s1.length-i)) &&
         isScramble(s1.substr(i), s2.substr(0,s1.length-i))) ) {
           return true
    }
  }
  return false
};