LC-0784 Medium LeetCode

784. Letter Case Permutation

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 75% Topics: String, Backtracking, Bit Manipulation

Reading material

Strings 12 min Backtracking 14 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n * 2^n)
# Space: O(n * 2^n)

class Solution(object):
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        result = [[]]
        for c in S:
            if c.isalpha():
                for i in xrange(len(result)):
                    result.append(result[i][:])
                    result[i].append(c.lower())
                    result[-1].append(c.upper())
            else:
                for s in result:
                    s.append(c)
        return map("".join, result)

Solution from kamyu104/LeetCode-Solutions · MIT