Search

Letter Case Permutation

Updated: Mar 25, 2021

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.


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"]

Constraints:

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

  • S will consist only of letters or digits.

Solution:

Iterative:


class Solution {
    Set<String> set = new HashSet<>();
    Queue<String> queue = new LinkedList();
    
    public List<String> letterCasePermutation(String s) 
    {
        queue.add(s);
        while(!queue.isEmpty())
        {
            String ss = queue.remove();
            if(set.contains(ss)) continue;     
            set.add(ss);
            
            for(int i=0;i<ss.length();i++)
            {
                char[] a = ss.toCharArray();
                if(Character.isLetter(a[i]))
                {
                    if(Character.isUpperCase(a[i])) a[i] = Character.toLowerCase(a[i]);
                    else a[i] = Character.toUpperCase(a[i]);
                }
                              
                String temp = String.valueOf(a);
                if(!set.contains(temp)) queue.add(temp);      
            }
                
        }
            
        return new ArrayList(set);
    }
}


Recursive


class Solution {public List<String> letterCasePermutation(String S) {
        List<String> result = new ArrayList<>();
        char[] ch = S.toCharArray();
        permute(ch, result, 0);
        return result;
    }
    
    public void permute(char[] ch, List<String> result, int index) {
        result.add(new String(ch));
        for(int i=index; i< ch.length; i++) {
            char c = ch[i];
            if(Character.isLetter(c)) {
                ch[i] = getOpposite(c);
                permute(ch, result, i+1);
                ch[i] = c;
            }
        }
    }
    
    public char getOpposite(char c){
        return Character.isUpperCase(c) ? Character.toLowerCase(c) : Character.toUpperCase(c);
    }
}
9 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.