0784._Letter_Case_Permutation.md

784. Letter Case Permutation

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/letter-case-permutation/

内容描述

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"]
Note:

S will be a string with length between 1 and 12.
S will consist only of letters or digits.

解题方案

思路 1 - 时间复杂度: O(2^N)- 空间复杂度: O(1)******

很简单的dfs, beats 45.03%

class Solution:
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        def dfs(s, idx):
            if idx == len(s):
                return
            dfs(s, idx+1)
            if not s[idx].isdigit():
                if ord(s[idx]) <= ord('Z'):
                    self.res.add(s[:idx]+s[idx].lower()+s[idx+1:])
                    dfs(s[:idx]+s[idx].lower()+s[idx+1:], idx+1)
                else:
                    self.res.add(s[:idx]+s[idx].upper()+s[idx+1:])
                    dfs(s[:idx]+s[idx].upper()+s[idx+1:], idx+1)
        if not S or len(S) == 0:
            return ['']
        self.res = set([S])
        dfs(S, 0)
        return list(self.res)