Letter Case Permutation

medium backtracking dfs strings

Problem

Given a string, return all possible strings obtained by toggling the case of each letter (digits unchanged).

Inputs='a1b2'

Output['a1b2','a1B2','A1b2','A1B2']

Each letter has two case choices.

input

def letterCasePermutation(s):
    res = []
    def dfs(i, cur):
        if i == len(s):
            res.append("".join(cur)); return
        if s[i].isalpha():
            cur.append(s[i].lower()); dfs(i+1, cur); cur.pop()
            cur.append(s[i].upper()); dfs(i+1, cur); cur.pop()
        else:
            cur.append(s[i]); dfs(i+1, cur); cur.pop()
    dfs(0, [])
    return res

function letterCasePermutation(s) {
  const res = [];
  function dfs(i, cur) {
    if (i === s.length) { res.push(cur); return; }
    if (/[a-zA-Z]/.test(s[i])) {
      dfs(i+1, cur + s[i].toLowerCase());
      dfs(i+1, cur + s[i].toUpperCase());
    } else dfs(i+1, cur + s[i]);
  }
  dfs(0, "");
  return res;
}

List<String> res = new ArrayList<>();
List<String> letterCasePermutation(String s) {
    dfs(s, 0, new StringBuilder());
    return res;
}
void dfs(String s, int i, StringBuilder cur) {
    if (i == s.length()) { res.add(cur.toString()); return; }
    char c = s.charAt(i);
    if (Character.isLetter(c)) {
        cur.append(Character.toLowerCase(c)); dfs(s, i+1, cur); cur.deleteCharAt(cur.length()-1);
        cur.append(Character.toUpperCase(c)); dfs(s, i+1, cur); cur.deleteCharAt(cur.length()-1);
    } else {
        cur.append(c); dfs(s, i+1, cur); cur.deleteCharAt(cur.length()-1);
    }
}

vector<string> res;
void dfs(string& s, int i, string& cur) {
    if (i == (int)s.size()) { res.push_back(cur); return; }
    if (isalpha(s[i])) {
        cur.push_back(tolower(s[i])); dfs(s, i+1, cur); cur.pop_back();
        cur.push_back(toupper(s[i])); dfs(s, i+1, cur); cur.pop_back();
    } else {
        cur.push_back(s[i]); dfs(s, i+1, cur); cur.pop_back();
    }
}
vector<string> letterCasePermutation(string s) {
    string cur;
    dfs(s, 0, cur);
    return res;
}

Explanation

For each character we ask one question: is it a letter or a digit? A letter can be lowercase or uppercase, giving two branches; a digit has only one form, so it just passes through. Exploring those choices position by position yields every variation.

The DFS dfs(i, cur) walks index i across the string while cur holds the characters chosen so far. When i reaches the end, cur is a complete string and gets saved.

At a letter we recurse twice: once with the lowercase form and once with the uppercase form. At a digit we recurse once, keeping it unchanged. (In the Python and Java/C++ versions we append, recurse, then pop to undo — the standard backtracking cleanup.)

Because each letter doubles the count and digits don't, a string with L letters produces 2^L results.

Example: "a1b2" has two letters. The a can be a or A, the b can be b or B, and the digits stay fixed, giving ["a1b2","a1B2","A1b2","A1B2"].

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