# Letter Case Permutation

• My Approach using Recursive Method:
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> res = new ArrayList<String>();
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);
} else if(c >=97 && c <=122) {
sArray[i] =(char) (c - 32);
}
sArray = S.toCharArray();

``````    }
return res;

}
``````

}

• 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;
}
};
``````

• 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
``````

• 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
``````

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

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