LC 784

Solution to LeetCode 784 Letter Case Permutation.

LeetCode 784

Letter Case Permutation (Medium). [link]

1] Recursion - DFS.

The idea of DFS here: the leaves of the tree are the results.

Time complexity O(n*2^l), where l is the number of letters in the string. The space complexity O(n)+O(n*2^l).

class Solution(object):
    def letterCasePermutation(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        n = len(s)
        def DFS(index, string):
            if index == n: 
                res.append(string)
                return 
            if string[index].islower():
                DFS(index + 1, string[:index] + chr(ord(string[index]) - 32) + string[index+1:])
            if string[index].isupper():
                DFS(index + 1, string[:index] + chr(ord(string[index]) + 32) + string[index+1:])
            DFS(index + 1, string)
        DFS(0, s)
        return res

Note: ASCII:

• Upper case A-Z: 65 - 90
• Lower case a-z: 98 - 122
• ‘a’ - ‘A’ = 32

Alternatively, we can use python functions .upper() and .lower().

class Solution(object):
    def letterCasePermutation(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        n = len(s)
        def DFS(index, string):
            if index == n: 
                res.append(string)
                return 
            if string[index].islower():
                DFS(index + 1, string[:index] + string[index].upper() + string[index+1:])
            if string[index].isupper():
                DFS(index + 1, string[:index] + string[index].lower() + string[index+1:])
            DFS(index + 1, string)
        DFS(0, s)
        return res

Slicing helps to avoid using ‘index’ variable.

class Solution(object):
    def letterCasePermutation(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        def DFS(string, path):
            if not string: 
                res.append(path)
                return
            if string[0].isalpha():
                DFS(string[1:], path + string[0].upper())
                DFS(string[1:], path + string[0].lower())
            else:
                DFS(string[1:], path + string[0])
        DFS(s, '')
        return res

2] Iteration.

class Solution(object):
    def letterCasePermutation(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = [""]
        for i in s:
            if i.isalpha():
                res = [word + j for word in res for j in [i.lower(), i.upper()]]
            else:
                res = [word + i for word in res]
        return res