LeetCode #784 Letter Case Permutation

Posted on | Post modified | In , , , , , , , , ,

Problem

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

1
2
3
4
5
6
7
8
9
Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

Note

  • S will be a string with length at most 12.
  • S will consist only of letters or digits.

Solution1

Method: Backtracking

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def __init__(self):
        self.res = []

    def backtrack(self, answer, kth, info):
        if kth == len(info):
            self.res.append(''.join(answer))
        else:
            candidates = []
            if info[kth].isdigit():
                candidates += [info[kth]]
            else:
                candidates += [info[kth].lower(), info[kth].upper()]

            kth += 1
            
            for candidate in candidates:
                answer.append(candidate)
                self.backtrack(answer, kth, info)
                answer.pop()

    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        self.backtrack([], 0, S)
        
        return self.res

Solution2 (much faster))

Method: Backtracking

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        res = ['']
        for ch in S:
            if ch.isalpha():
                res = [i+j for i in res for j in [ch.upper(), ch.lower()]]
            else:
                res = [i+ch for i in res]
        return res