Letter Case Permutation | February Leetcoding challenge 2021 | Day 16
logo
Manas Sinha
Developer | Designer

By Manas | 16 February 2021

February LeetCoding Challenge 2021

Day 16

Letter Case Permutation

PROBLEM  STATEMENT:
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.

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"]
Constraints:
  • S will be a string with length between 1 and 12.
  • S will consist only of letters or digits.

Explanation

This problem can be solved using backtracking approach.
ALGORITHM:
  • Start processing the string from left to right.
  • Base case : If you reach the last index of the string, add the string generated to the result array and terminate.
  • Append the current character the temporary string (we don’t need to check if its an alphabet or number) and make a recursive call for next index.
  • Now if the current charachter is a lowercase alphabet we append its uppercase to the temporary string else the lowercase. And make a recursive call for next index.
  • Doing this, if the current character was numeric there will be only one recursive call (step 3) and if its an alphabet there will be another call (step 4).
Analysis of output for : a1b2

current string : 
current string : a
current string : a1
current string : a1b
current string : a1b2

pushing string : a1b2

reverted back to : a1b
reverted back to : a1

changing case of b

current string : a1B
current string : a1B2

pushing string : a1B2

reverted back to : a1B
reverted back to : a1
reverted back to : a
reverted back to : 

changing case of a

current string : A
current string : A1
current string : A1b
current string : A1b2

pushing string : A1b2

reverted back to : A1b
reverted back to : A1

changing case of b

current string : A1B
current string : A1B2

pushing string : A1B2

reverted back to : A1B
reverted back to : A1
reverted back to : A
reverted back to : 

Exit

code

class Solution {
public:
    vector<string> res;
    void solve(string s,int i=0,string temp=""){
        if(i == s.size()){
            res.push_back(temp);
            return;
        }
        
        solve(s,i+1,temp+s[i]);
        int diff = 'a'-'A';
        if(s[i]>='a' && s[i]<='z')
        {
            char c = (s[i]-diff);
            solve(s,i+1,temp+c);
        }
        else if(s[i]>='A' && s[i]<='Z'){
            char c = (s[i]+diff);
            solve(s,i+1,temp+c);
        }
    }
    vector<string> letterCasePermutation(string S) {
        solve(S);
        return res;
    }
};

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply