Quick-n-easy 7-liner in Python

  • 0

    Quick-and-easy Python solution to code up at interview before going for more efficient solutions. Runtime is huge due to slicing.

    class Solution(object):
        def numDistinct(self, s, t, memo={}, res=0):
            if not t:           return 1
            if not s and t:     return 0
            if (s, t) in memo:  return memo[s, t]
            for i in range(len(s)):
                if t[0] == s[i]: res += self.numDistinct(s[i+1:], t[1:], memo)
            memo[s,t] = res
            return memo[s,t]
    # 63 / 63 test cases passed.
    # Status: Accepted
    # Runtime: 1468 ms

Log in to reply

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