784. Letter Case Permutation

Description

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 12
s consists of lowercase English letters, uppercase English letters, and digits.

Solutions

Solution 1: DFS

Since each letter in \(s\) can be converted to uppercase or lowercase, we can use the DFS (Depth-First Search) method to enumerate all possible cases.

Specifically, traverse the string \(s\) from left to right. For each letter encountered, you can choose to convert it to uppercase or lowercase, and then continue to traverse the subsequent letters. When you reach the end of the string, you get a conversion scheme and add it to the answer.

The method of converting case can be implemented using bitwise operations. For a letter, the difference between the ASCII codes of its lowercase and uppercase forms is \(32\), so we can achieve case conversion by XORing the ASCII code of the letter with \(32\).

The time complexity is \(O(n \times 2^n)\), where \(n\) is the length of the string \(s\). For each letter, we can choose to convert it to uppercase or lowercase, so there are \(2^n\) conversion schemes in total. For each conversion scheme, we need \(O(n)\) time to generate a new string.

Python3JavaC++GoTypeScriptRust

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        def dfs(i: int) -> None:
            if i >= len(t):
                ans.append("".join(t))
                return
            dfs(i + 1)
            if t[i].isalpha():
                t[i] = chr(ord(t[i]) ^ 32)
                dfs(i + 1)

        t = list(s)
        ans = []
        dfs(0)
        return ans

class Solution {
    private List<String> ans = new ArrayList<>();
    private char[] t;

    public List<String> letterCasePermutation(String s) {
        t = s.toCharArray();
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i >= t.length) {
            ans.add(new String(t));
            return;
        }
        dfs(i + 1);
        if (Character.isLetter(t[i])) {
            t[i] ^= 32;
            dfs(i + 1);
        }
    }
}

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        string t = s;
        vector<string> ans;
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if (i >= t.size()) {
                ans.push_back(t);
                return;
            }
            dfs(i + 1);
            if (isalpha(t[i])) {
                t[i] ^= 32;
                dfs(i + 1);
            }
        };
        dfs(0);
        return ans;
    }
};

func letterCasePermutation(s string) (ans []string) {
    t := []byte(s)
    var dfs func(int)
    dfs = func(i int) {
        if i >= len(t) {
            ans = append(ans, string(t))
            return
        }
        dfs(i + 1)
        if t[i] >= 'A' {
            t[i] ^= 32
            dfs(i + 1)
        }
    }

    dfs(0)
    return ans
}

function letterCasePermutation(s: string): string[] {
    const t = s.split('');
    const ans: string[] = [];
    const dfs = (i: number) => {
        if (i >= t.length) {
            ans.push(t.join(''));
            return;
        }
        dfs(i + 1);
        if (t[i].charCodeAt(0) >= 65) {
            t[i] = String.fromCharCode(t[i].charCodeAt(0) ^ 32);
            dfs(i + 1);
        }
    };
    dfs(0);
    return ans;
}

impl Solution {
    pub fn letter_case_permutation(s: String) -> Vec<String> {
        fn dfs(i: usize, t: &mut Vec<char>, ans: &mut Vec<String>) {
            if i >= t.len() {
                ans.push(t.iter().collect());
                return;
            }
            dfs(i + 1, t, ans);
            if t[i].is_alphabetic() {
                t[i] = (t[i] as u8 ^ 32) as char;
                dfs(i + 1, t, ans);
            }
        }

        let mut t: Vec<char> = s.chars().collect();
        let mut ans = Vec::new();
        dfs(0, &mut t, &mut ans);
        ans
    }
}

Solution 2: Binary Enumeration

For a letter, we can convert it to uppercase or lowercase. Therefore, for each letter, we can use a binary bit to represent its conversion scheme, where \(1\) represents lowercase and \(0\) represents uppercase.

First, we count the number of letters in the string \(s\), denoted as \(n\). Then, there are \(2^n\) conversion schemes in total. We can use each bit of a binary number to represent the conversion scheme of each letter, enumerating from \(0\) to \(2^n-1\).

Specifically, we can use a variable \(i\) to represent the current binary number being enumerated, where the \(j\)-th bit of \(i\) represents the conversion scheme of the \(j\)-th letter. That is, the \(j\)-th bit of \(i\) being \(1\) means the \(j\)-th letter is converted to lowercase, and \(0\) means the \(j\)-th letter is converted to uppercase.