Problem Statement:
You are given a string, you need to transform every letter individually to be lowercase or uppercase to create another string.
Example
Input: "a1b" Output: "a1b", "A1b", "a1B", "A1B"
Solution
We can solve this problem by using DFS method.
Explanations is as below:
a1b2 i=0 = a, as it is a letter, we have two branches: a, A / \ a1b2 A1b2 i=1 = 1, we only have 1 branch that is itself | | a1b2 A1b2 i=2 = b, we have two branches: b, B / \ / \ a1b2 a1B2 A1b2 A1B2 i=3 = S.length(), we end the recursion here.
Solution in C++
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<vector> #include<set> using namespace std; void backtrace( string S, int i, vector<string> &result ) { if( i == S.length() ) { result.push_back( S ); return; } if( 'a' <= S[i] && S[i] <= 'z' ) { backtrace( S, i + 1, result ); S[i] = 'A' + S[i] - 'a'; backtrace( S, i + 1, result ); } else if ( 'A' <= S[i] && S[i] <= 'Z' ) { backtrace( S, i + 1, result ); S[i] = 'a' + S[i] - 'A'; backtrace( S, i + 1, result ); } else { backtrace( S, i + 1, result ); } } vector<string> letter_case_permutation( string S ) { vector<string> result; backtrace( S, 0, result ); return result; } int main() { vector<string> result = letter_case_permutation("a1b"); cout<<"Result = "<<endl; for (int i = 0; i < result.size(); i++) { cout<<result[i]<<" "; } return 0; } /* vector<vector<int> > result = combine(n, k); cout<<"Result = "<<endl; for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { cout << result[i][j] << " "; } cout << endl; } */
Output:
Result = a1b a1B A1b A1B