Share a Python solution and a question regarding empty string in Set()


  • 0

    Here is my DP solution in Python using a dictionary that maps current remaining string to a set of all possible compositions of words of this string:

    def wordBreak(self, s, wordDict):
        cache = {"": set(" ")}
        """ in python, a set with an empty string is considered empty
        """
        def parse(remain, l):
            if remain in cache:
                return cache[remain]
    
            cache[remain] = set()
            for i in range(1, len(remain)+1):
                if remain[:i] in wordDict:
                    rest = parse(remain[i:], l + remain[:i] + ' ')
                    if rest:
                        for k in rest:
                            cache[remain].add(remain[:i] + ' ' + k)
    
            return cache[remain]
    
        res = parse(s, "")
        ret = []
        for i in res:
            ret.append(i[:-2])  # remove 2 extra ' '
        return ret
    

    However, I'm not sure I understand why len(set('')) is 0 in python. From my perspective, it makes sense to declare a set as empty when nothing is in it but not when an empty string is in it. Any one have an idea?


  • 0
    S

    you can try this
    print len(set(['']))


Log in to reply
 

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