# Quick-n-easy 9-liner in Python

• Not great runtime because of string slicing and everything, but at the interview we must code quickly so this could be a great starting point that leads to bottom-up solution.

``````class Solution(object):
def isScramble(self, s, t, memo={}):
if len(s) != len(t):  return False
if len(s) <= 1:       return s == t
if (s, t) in memo:    return memo[s, t]
for i in range(1, len(s)):
if (self.isScramble(s[:i], t[-i:], memo) and self.isScramble(s[i:], t[:-i], memo)) or\
(self.isScramble(s[:i], t[:i], memo) and self.isScramble(s[i:], t[i:], memo)):
memo[s,t] = True
return True
memo[s, t] = False
return False

# 281 / 281 test cases passed.
# Status: Accepted
# Runtime: 376 ms
``````

• len(s) != len(t)

Try something better here.

• @StefanPochmann you mean `if Counter(s1) != Counter(s2: return False)`?

• @agave Yes, or `sorted`, which is faster here.

Btw, I noticed you always explicitly pass the default parameter `memo`. Do you do that because you want to for some reason or because you think you need to?

• @StefanPochmann I need to define it somewhere, right?

• @agave Yes, but I'm talking about the explicit passing. In the four recursive calls.

• @StefanPochmann how would you do it?

• @agave I'd just remove the "`, memo`" from the four calls.

• @StefanPochmann not sure how the memo would be passed to the recursive calls... if I don't pass it, they would get the empty memo right?

• @agave Well you don't need to pass it, because it's the default. And initially it's empty, yes, but then you're filling it.

Maybe a smaller example is clearer?

``````>>> def fibonacci(n, memo={}):
if n < 2:
return n
if n not in memo:
memo[n] = fibonacci(n - 2) + fibonacci(n - 1)
return memo[n]

>>> fibonacci(300)
222232244629420445529739893461909967206666939096499764990979600L
``````

• @StefanPochmann OK, I didn't know that the local parameter `memo` would be implicitly passed to the recursive calls...

• @agave I guess you can think of it as implicit passing, though I'd say it really is simply the default value. Which gets used when nothing gets passed.

Another example, without recursion:

``````>>> def test(n, a=[]):
a.append(n)
return sum(a)

>>> test(4)
4
>>> test(7)
11
>>> test(100)
111
``````

• @StefanPochmann ok this is cool but a bit confusing. Where is the `a` array in memory? I thought that `a` is created in `test()`'s stack and then destroyed, but seems I am wrong since it is persistent... But then when you try to print `a` from the console outside the function, Python says it's not defined.

Possibly I should read something about how Python handles local and global parameters.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.