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

Input: S = "3z4"

Output: ["3z4", "3Z4"]

Example 3

Input: S = "12345"

Output: ["12345"]

Example 4

Input: S = "0"

Output: ["0"]

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

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private List<String> resultList;
    
    public List<String> letterCasePermutation(String S) {
        resultList = new ArrayList();
        letterCasePermutationHelper(S, S.length(), 0, new StringBuilder());
        return resultList;
    }
    
    private void letterCasePermutationHelper(String s, int n, int index, StringBuilder sb) {
        if(index == n) {
            resultList.add(sb.toString());
            return;
        }
        
        char ch = s.charAt(index);
        
        if(Character.isDigit(ch)) {
            sb.append(ch);
            letterCasePermutationHelper(s, n, index+1, sb);
            sb.deleteCharAt(sb.length()-1);
        } else {
            sb.append(Character.toLowerCase(ch));
            letterCasePermutationHelper(s, n, index+1, sb);
            sb.deleteCharAt(sb.length()-1);

            sb.append(Character.toUpperCase(ch));
            letterCasePermutationHelper(s, n, index+1, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

Follow up