Solution: Letter Case Permutation
Tags: algorithms, javascript, java, python
Published: 2021-02-16 23:30:47

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/letter-case-permutation/discuss/1069003/).*

---

####[Leetcode Problem #784 (*Medium*): Letter Case Permutation](https://leetcode.com/problems/letter-case-permutation/)

---

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

---

***Examples:***

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.

---

***Idea:***

When a problem asks us to deal with permutations, one of the obvious approaches is via **recursion** as recursion will allow us to fire off our helper function down each  branching possibility.

Recursion also naturally favors a **DFS** approach, which is also good because it ensures that our recursion stack never gets too deep.

Our recursive helper function (**dfs**) is actually quite simple. If we start with the input string (**S**) fully lowercased, then we just need to make sure that each version of **dfs** calls itself down two branches: one in which the current character is left unchanged, and a second in which the character has been uppercased, but only if the character is a letter.

Then, whenever we reach the end of **S**, we can add the permutation to our answer array (**ans**).

---

***Implementation:***

Javascript and Python deal with string copies faster than character arrays, so **dfs** will maintain a string (**res**) that it will build up as the function is called recursively.

Java deals with char arrays faster than it does strings, so we can pass a reference to a singular central char array (**chArr**) and modify it as we go. This also means that we have to remember to undo our **toUpperCase** after the second **dfs** is fired off so that later recursions reaching this character start with it in lower case.

C++ alone out of the four languages has mutable strings, so we can just pass a full copy of **S** down and modify each char individually, rather than having to build out a **res**.

---

***Javascript Code:***
```javascript
var letterCasePermutation = function(S) {
    S = S.toLowerCase()
    let len = S.length, ans = []
    const dfs = (i, res='') => {
        if (i < len) {
            dfs(i+1, res + S[i])
            if (S[i] >= 'a') dfs(i+1, res + S[i].toUpperCase())
        } else ans.push(res)
    }
    dfs(0)
    return ans
};
```

---

***Python Code:***
```python
class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        S = S.lower()
        lenS, ans = len(S), []
        def dfs(i, res=''):
            if i < lenS:
                dfs(i+1, res + S[i])
                if S[i].islower(): dfs(i+1, res + S[i].upper())
            else: ans.append(res)
        dfs(0)
        return ans
```

---

***Java Code:***
```java
class Solution {
    public List<String> letterCasePermutation(String S) {
        List ans = new ArrayList();
        dfs(S.toLowerCase().toCharArray(), ans, 0, S.length());
        return ans;
    }
    public void dfs(char[] chArr, List ans, int i, int len) {
        if (i < len) {
            dfs(chArr, ans, i+1, len);
            if (Character.isLetter(chArr[i])) {
                chArr[i] = Character.toUpperCase(chArr[i]);
                dfs(chArr, ans, i+1, len);
                chArr[i] = Character.toLowerCase(chArr[i]);
            }
        } else ans.add(new String(chArr));
    }
}
```

---

***C++ Code:***
```c++
class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        for (int i = 0; i < S.size(); i++) S[i] = tolower(S[i]);
        vector<string> ans;
        dfs(S, ans, 0, S.size());
        return ans;
    }
    void dfs(string S, vector<string> &ans, int i, int len) {
        if (i < len) {
            dfs(S, ans, i+1, len);
            if (isalpha(S[i])) {
                S[i] = toupper(S[i]);
                dfs(S, ans, i+1, len);
            }
        } else ans.push_back(S);
    }
};
```