Algorithm
Problem Name: 784. Letter Case Permutation
Problem Link: https://leetcode.com/problems/letter-case-permutation/
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. Return the output in any order.
Example 1:
Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"]
Example 2:
Input: s = "3z4" Output: ["3z4","3Z4"]
Constraints:
1 <= s.length <= 12sconsists of lowercase English letters, uppercase English letters, and digits.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> letterCasePermutation(string S) {
vector<string>res;
DFS(S, 0, res);
return res;
}
void DFS(string S, int pos, vector < string>& res){
if(pos == S.size()){
res.push_back(S);
return;
}
DFS(S, pos + 1, res);
char c = S[pos];
if(isalpha(c)){
S[pos] = islower(c) ? toupper(c) : tolower(c);
DFS(S, pos + 1, res);
}
}
};
Input
s = "a1b2"
Output
["a1b2","a1B2","A1b2","A1B2"]
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const letterCasePermutation = function(S) {
let res = []
backtrack(res, "", 0, S)
return res
};
const backtrack = (res, sol, depth, S) => {
if (depth == S.length) {
res.push(sol)
return
}
const c = S[depth]
if ("1234567890".indexOf(c) != - 1) {
backtrack(res, sol+c, depth + 1, S)
} else {
backtrack(res, sol+c.toLowerCase(), depth + 1, S)
backtrack(res, sol+c.toUpperCase(), depth + 1, S)
}
}
console.log(letterCasePermutation("a1b2"))
console.log(letterCasePermutation("3z4"))
console.log(letterCasePermutation("12345"))
Input
s = "a1b2"
Output
["a1b2","a1B2","A1b2","A1B2"]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def letterCasePermutation(self, S: str) -> List[str]:
bfs = ['']
for c in S:
if c.isdigit():
bfs = [s + c for s in bfs]
else:
bfs = [s + c.lower() for s in bfs] + [s + c.upper() for s in bfs]
return bfs
Input
s = "3z4"
Output
["3z4","3Z4"]
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0784_LetterCasePermutation
{
public IList < string> LetterCasePermutation(string S)
{
List result = new List();
BackTracking(S, "", result, 0);
return result;
}
public void BackTracking(string input, string current, List < string> result, int index)
{
if (current.Length == input.Length)
{
result.Add(new string(current.ToCharArray()));
return;
}
char ch = input[index];
if (char.IsDigit(ch))
{
current = string.Concat(current, ch);
BackTracking(input, current, result, index + 1);
}
else
{
BackTracking(input, current + char.ToLower(ch), result, index + 1);
BackTracking(input, current + char.ToUpper(ch), result, index + 1);
}
}
}
}
Input
s = "3z4"
Output
["3z4","3Z4"]