# 784. Letter Case Permutation
- [home](/@Giting/home)

## 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.

Examples:

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

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

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

Note:

S will be a string with length between 1 and 12.
S will consist only of letters or digits.

## Solution

### 1. Permutation

* Time complexity: O(2^n)
* Space complexity: O(2^n)

// a b c s
// A b c s
        
// a B c 0 
// A B c 1
        
// a b C 0
// a B C 2
// A b C 1
// A B C 3

char ** letterCasePermutation(char *s, int* returnSize){

    *returnSize = 1;
    int str_len = 0;

    // O(n)
    for(int i = 0; s[i] != '\0'; ++i)
    {
        str_len++;
        if ((s[i] <= 'z' && s[i] >= 'a') || (s[i] <= 'Z' && s[i] >= 'A'))
        {
            *returnSize = *returnSize * 2;
        }
    }

    char **ans = malloc(sizeof(char *) * *returnSize);
    if (*returnSize == 1)
    {
        ans[0] = s;
        return ans;
    }

    int idx = 0;
    char *tmp;

    // O(n)
    for(int i = 0; s[i] != '\0'; ++i)
    {
        if (s[i] <= '9' && s[i] >= '0')
            continue;

        int j = 0;

        if (idx == 0)
        {
            tmp = malloc(sizeof(char) * (str_len + 1));
            strcpy(tmp, s);
            ans[idx++] = tmp;

            tmp = malloc(sizeof(char) * (str_len + 1));
            strcpy(tmp, s);
            ans[idx++] = tmp;

            j = 1;
        }
        else
        {
            int cnt = idx;
            do{
                tmp = malloc(sizeof(char) * (str_len + 1));
                strcpy(tmp, ans[j++]);
                ans[idx++] = tmp;

            } while(j < cnt);

        }

        do{
            if (s[i] <= 'z' && s[i] >= 'a')
            {
                ans[idx - j][i] = s[i] - 'a' + 'A';
            }
            else if (s[i] <= 'Z' && s[i] >= 'A')
            {
                ans[idx - j][i] = s[i] - 'A' + 'a';
            }

            j--;
        } while(j > 0);

    }

    return ans;
}

| Status | Runtime | Memory |
| -------- | -------- | -------- |
| Accepted | 8 ms | 9.8 MB |

###### tags: `c` `leetcode` `easy` `permutation` `string` `backtracking` `bit manipulation`