首页 > itarticle > algorithm notes: leetcode#784 letter case permutation

algorithm notes: leetcode#784 letter case permutation

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        ans = ['']
        
        for c in S:
            if c.isalpha():
                ans = [t+c.lower() for t in ans] + [t+c.upper() for t in ans]
            else:
                ans = [t+c for t in ans]
        return ans

Java implementation

class  {
    public List<String> letterCasePermutation(String S) {
        List<String> ans = new ArrayList<>();
        ans.add("");
        
        for(char c : S.toCharArray()){
            if(Character.isLetter(c)){
                List<String> newAns = new ArrayList<>();
                for(String t : ans){
                    newAns.add(t+Character.toString(Character.toLowerCase(c)));
                    newAns.add(t+Character.toString(Character.toUpperCase(c)));
                }
                ans = newAns;
            }else{
                for(int i = 0; i < ans.size(); i++){
                    ans.set(i, ans.get(i) + Character.toString(c));
                }
            }
        }
        return ans;
    }
}

Time complexity

O(2^N * N).

Space complexity

O(2^N * N).

Links

784. Letter Case Permutation
(中文版) 算法笔记: 力扣#784 字母大小写全排列