Letter Case Permutation


  • 0

    Click here to see the full article post


  • 0
    M

    My Approach using Recursive Method:
    class Solution {
    public List<String> letterCasePermutation(String S) {
    List<String> res = new ArrayList<String>();
    res.add(S);
    int c;
    char[] sArray = S.toCharArray();
    for(int i=0; i < sArray.length ; i++) {
    c = sArray[i];
    if(c >= 65 && c <= 90) {
    sArray[i] =(char) (c + 32);
    res.add(String.valueOf(sArray));
    } else if(c >=97 && c <=122) {
    sArray[i] =(char) (c - 32);
    res.add(String.valueOf(sArray));
    }
    sArray = S.toCharArray();

        }
        return res;
        
    }
    

    }


  • 0
    J

    Without recursion, not terribly space efficient:

    class Solution {
    public:
        vector<string> letterCasePermutation(string S) {
            vector<string> output;
            output.push_back("");
            
            for(char c : S){
                if(isalpha(c)){
                    vector<string> temp;
                    for(auto o : output){
                        temp.push_back(o + (char) toupper(c));
                        temp.push_back(o + (char) tolower(c));
                    }
                    output = temp;
                }else{
                    for(auto &o : output){
                        o += c;
                    }
                }
            }
            return output;
        }
    };
    

  • 0
    A

    Found this online. Best Recursive Solution

        def capitalization_permutations(self,s):
            """Generates the different ways of capitalizing the letters in
            the string s.
    
            list(capitalization_permutations('abc'))
            ['ABC', 'aBC', 'AbC', 'abC', 'ABc', 'aBc', 'Abc', 'abc']
            list(capitalization_permutations(''))
            ['']
            list(capitalization_permutations('X*Y'))
            ['X*Y', 'x*Y', 'X*y', 'x*y']
            """
            if s == '':
                yield ''
                return
            for rest in self.capitalization_permutations(s[1:]):
                yield s[0].upper() + rest
                if s[0].upper() != s[0].lower():
                    yield s[0].lower() + rest
    

  • 1

    We can also solve it by DFS/BFS

    ## Blog link: https://brain.dennyzhang.com/letter-case-permutation
    class Solution:
        ## Basic Ideas: One pass (similar like DFS)
        ##
        ## Complexity: Time O(n*pow(2,n)), Space O(pow(2, n))
        def letterCasePermutation(self, S):
            """
            :type S: str
            :rtype: List[str]
            """
            res = [""]
            for ch in S:
                l = []
                for item in res:
                    if ch.isdigit():
                        l.append("%s%s" % (item, ch))
                    else:
                        l.append("%s%s" % (item, ch.lower()))
                        l.append("%s%s" % (item, ch.upper()))
                res = l
            return res
            
        ## Basic Ideas: BFS
        ##
        ## Complexity: Time O(n*pow(2, n)), Space O(pow(2, n))
        def letterCasePermutation_v1(self, S):
            """
            :type S: str
            :rtype: List[str]
            """
            length = len(S)
            if length == 0: return [""]
            import collections
            queue = collections.deque()
            queue.append("")
            level = -1
            while True:
                level += 1
                if level == length: break
                for k in range(len(queue)):
                    ch = S[level]
                    element = queue.popleft()
                    if ch.isdigit():
                        queue.append("%s%s" % (element, ch))
                    else:
                        queue.append("%s%s" % (element, ch.lower()))
                        queue.append("%s%s" % (element, ch.upper()))
            return list(queue)
                
        ## Basic Ideas: recursive
        ##
        ## Complexity: Time O(n*pow(2, n)), Space O(pow(2, n))
        def letterCasePermutation_v1(self, S):
            """
            :type S: str
            :rtype: List[str]
            """
            length = len(S)
            if length == 0: return [""]
            res = []
            ch = S[0]
            for item in self.letterCasePermutation(S[1:]):
                if ch.isdigit():
                    res.append("%s%s" % (ch, item))
                else:
                    res.append("%s%s" % (ch.lower(), item))
                    res.append("%s%s" % (ch.upper(), item))
            return res
    

  • 0
    Z

    No matter what kind of algorithms, the complexity is still O(2^N * N), why?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.