64ms python recursive solution


  • 1
    I
    import collections
    class Solution:
        # @return an integer
        def numDistinct(self, S, T):
            self.dic=collections.defaultdict(set)
            TS=set(T)
            for i,c in enumerate(S):
                if c in TS:
                    self.dic[c].add(i)
            return sum(self.search(T).viewvalues())
    
        def search(self, T):
            resDic=collections.defaultdict(int)
            if len(T)==1:
                for x in self.dic[T[0]]:
                    resDic[x]=1
            else:
                for index,count in self.search(T[0:-1]).items():
                    for a in self.dic[T[-1]]:
                        if a>index:
                            resDic[a]+=count
            return resDic

Log in to reply
 

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