Letter Case Permutation

Letter Case Permutation

Problem Statement

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.

Examples:

Input: S = “r2q”

Output: [“r2q”, “R2q”, “r2Q”, “R2Q”].

Input: S = “678”

Output: [“678”]

Note:

1. S will be a string with length between 1 and 12.
2. S will consist only of letters or digits.

Solution:

We don’t have to take care of digits as they can’t help to find more pernutations. We only have letters with us now. Suppose a string have L letters in it. The number of possible permutation will 2^L.

This can be represented by bitmask bits.

For Example: we have g5h, we can represent all the possible permutations as g5h = 00, g5H = 01, G7h = 10, G7H = 11. Digits given in the input string are not included in bitmask.

According the possible bitmask, find out all the permutations, taking one bitmask at a time.

Implementation


Java

class Solution {
    public List<String> letterCasePermutation(String S) {
        int B = 0;
        for (char c: S.toCharArray())
            if (Character.isLetter(c))
                B++;

        List<String> ans = new ArrayList();

        for (int bits = 0; bits < 1<<B; bits++) {
            int b = 0;
            StringBuilder word = new StringBuilder();
            for (char letter: S.toCharArray()) {
                if (Character.isLetter(letter)) {
                    if (((bits >> b++) & 1) == 1)
                        word.append(Character.toLowerCase(letter));
                    else
                        word.append(Character.toUpperCase(letter));
                } else {
                    word.append(letter);
                }
            }

            ans.add(word.toString());
        }

        return ans;

    }
}

Python

class Solution(object):
    def letterCasePermutation(self, S):
        f = lambda x: (x.lower(), x.upper()) if x.isalpha() else x
        return map("".join, itertools.product(*map(f, S)))

Complexity Analysis

• Time Complexity: O(2ⁿ*n).
• Space Complexity: O(2ⁿ*n).