[LeetCode] Letter Case Permutation

Problem: 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:

Input: S = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Input: S = "3z4"
Output: ["3z4","3Z4"]

Input: S = "12345"
Output: ["12345"]

Input: S = "0"
Output: ["0"]

Approach: We can follow the similar approach as our previous problem Print permutations of a string. We just use the recursion in the same way.

Implementation in C#:

    public IList<string> LetterCasePermutation(string S) 

    {

        List<string> result = new List<string>();

        if (S?.Length == 0)

        {

            return result; 

        }

        this.LetterCasePermutation(S.ToCharArray(), 0, ref result);

        return result;

    }

    

    private void LetterCasePermutation(char[] currStr, int index, ref List<string> result)

    {

        for (int i = index; i < currStr.Length; ++i)

        {

            if (char.IsDigit(currStr[i]))

            {

                continue;

            }

            this.ChangeLetterCase(currStr, i);

            this.LetterCasePermutation(currStr, i + 1, ref result);  

            this.ChangeLetterCase(currStr, i);

        }

        result.Add(new string(currStr));  

    }

    

    private void ChangeLetterCase(char[] currStr, int index)

    {

        if (char.IsUpper(currStr[index]))

        {

            currStr[index] = char.ToLower(currStr[index]);

        }

        else

        {

            currStr[index] = char.ToUpper(currStr[index]);

        }

    }

Complexity: O(n * 2 ^ n)