Solution: Letter Case Permutation

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #784 (Medium): 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:

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:

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:

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:

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);
    }
};

Comments

[Shubhranil Dutta]

Here's another solution. We can also use a Bit-Masking approach to solve this problem.

Solution.java

import java.util.ArrayList;
import java.util.List;

/**
 * * Letter Case Permutation
 */

public class Solution {
  /**
   * Helper function to check if
   * a character is a digit or not.
   */
  private boolean isDigit(char ch) {
    return Character.isDigit(ch);
  }

  /**
   * Helper function to toggle
   * the case of a character. 
   */
  private char toggleCharacterCase(char ch) {
    return Character.isLowerCase(ch) ?
      Character.toUpperCase(ch) :
      Character.toLowerCase(ch);
  }

  private void getPermutationsWithLetterCaseChange(
    String input, int index, String output, List<String> perms
  ) {
    /**
     * Base Case.
     * 
     * If index is equal to the
     * input length, then we've
     * found a potential output.
     */
    if (index == input.length()) {
      perms.add(output.toString());
      return;
    }

    char currentChar = input.charAt(index);

    // If the current character
    // is a digit, then we don't
    // need to perform any case
    // change. We just add it to
    // the output string.
    if (isDigit(currentChar)) {
      getPermutationsWithLetterCaseChange(input, index + 1, output + currentChar, perms);
    }
    else {
      // First, we first toggle the
      // case of the current character
      // and consider all possible
      // scenarios.
      getPermutationsWithLetterCaseChange(input, index + 1, output + toggleCharacterCase(currentChar), perms);

      // Second, we don't first toggle the
      // case of the current character
      // and consider all possible
      // scenarios.
      getPermutationsWithLetterCaseChange(input, index + 1, output + currentChar, perms);
    }
  }

  public List<String> getPermutationsWithLetterCaseChange(String string) {
    List<String> perms = new ArrayList<>();

    getPermutationsWithLetterCaseChange(string, 0, "", perms);

    return perms;
  }