784. Letter Case Permutation
1. Description
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. You can return the output in any order.
2. Example
Example 1:
Input: S = “a1b2”
Output: [“a1b2”,“a1B2”,“A1b2”,“A1B2”]
Example 2:
Input: S = “3z4”
Output: [“3z4”,“3Z4”]
Example 3:
Input: S = “12345”
Output: [“12345”]
Example 4:
Input: S = “0”
Output: [“0”]
3. Constraints
- S will be a string with length between 1 and 12.
- S will consist only of letters or digits.
4. Solutions
My Accepted Solution
Reference 78. Subsets
n = m_str.size(), m is the number of letters in m_str
Time complexity: O($n2^m$)
Space complexity: O($n2^m$)
class Solution
{
public:
// vector<string> letterCasePermutation(string S)
vector<string> letterCasePermutation(string &m_str)
{
// set all uppercase letters to lowercase letters
for(int i = 0; i < m_str.size(); i++)
{
if('A' <= m_str[i] && m_str[i] <= 'Z')
m_str[i] -= 'A' - 'a';
}
int letterCount = 0;
for(int i = 0; i < m_str.size(); i++)
{
if('a' <= m_str[i] && m_str[i] <= 'z')
letterCount++;
}
int resultSize = (1 << letterCount);
vector<string> result{m_str};
for(int i = 1; i < resultSize; i++)
{
string iter = m_str;
for(int j = 0, letterIndex = 0; j < iter.size(); j++)
{
if('a' <= iter[j] && iter[j] <= 'z')
{
if(i & (1 << letterIndex)) iter[j] += 'A' - 'a';
letterIndex++;
}
}
result.push_back(iter);
}
return result;
}
};