784. Letter Case Permutation

MediumView on LeetCode

String Backtracking Bit Manipulation

Time: O(2^n)

Space: O(2^n)

Intuition

Backtracking: for each character, if it's a letter, branch into lowercase and uppercase versions.

Algorithm

1Recursive DFS: at each position, if digit add as-is. If letter, recurse with lower and upper case.
2Base case: position == length → add to results.

Common Pitfalls

•Digits are added without branching. Converting between cases: XOR with 32.

784.cs

// Approach: DFS backtracking; at each letter position branch into both lowercase and uppercase variants.
// Time: O(2^n) Space: O(2^n)

public class Solution
{
    public IList<string> LetterCasePermutation(string s)
    {
        List<string> ans = new List<string>();
        Dfs(new StringBuilder(s), 0, ans);
        return ans;
    }

    private void Dfs(StringBuilder sb, int i, List<string> ans)
    {
        if (i == sb.Length)
        {
            ans.Add(sb.ToString());
            return;
        }
        if (char.IsDigit(sb[i]))
        {
            Dfs(sb, i + 1, ans);
            return;
        }

        sb[i] = char.ToLower(sb[i]);
        Dfs(sb, i + 1, ans);
        sb[i] = char.ToUpper(sb[i]);
        Dfs(sb, i + 1, ans);
    }
}

Was this solution helpful?