# Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.
#   Return a list of all possible strings we could create.
#
# Examples:
# Input: S = "a1b2"
# Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
#
# Input: S = "3z4"
# Output: ["3z4", "3Z4"]
#
# Input: S = "12345"
# Output: ["12345"]


class Solution(object):
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        res = [S]

        def helper(pos, t):
            if pos == len(t):
                return
            for i in xrange(pos, len(t)):
                if t[i].isalpha():
                    if t[i].islower():
                        s = t[0:i] + t[i].upper() + t[i + 1:]
                        res.append(s)
                        helper(i + 1, s)
                    else:
                        s = t[0:i] + t[i].lower() + t[i + 1:]
                        res.append(s)
                        helper(i + 1, s)

        helper(0, S)

        return res


if __name__ == '__main__':
    print Solution().letterCasePermutation("")
    print Solution().letterCasePermutation("a1b2")
