784. 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.

Constraints

• S will be a string with length between 1 and 12.

• S will consist only of letters or digits.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: S = "a1b2"

Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Example 2

Example 3

Example 4

Solutions

Solution 1

/**
 * Time complexity : O(2^N * N), where N is the length of S. 
 *    This reflects the cost of writing the answer.
 * Space complexity : O(2^N * N)
 */

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<StringBuilder> ans = new ArrayList();
        ans.add(new StringBuilder());

        for (char c: S.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.add(new StringBuilder(ans.get(i)));
                    ans.get(i).append(Character.toLowerCase(c));
                    ans.get(n+i).append(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; ++i)
                    ans.get(i).append(c);
            }
        }

        List<String> finalans = new ArrayList();
        for (StringBuilder sb: ans)
            finalans.add(sb.toString());
        return finalans;
    }
}

Solution 2

Follow up