784.Letter Case Permutation

Posted on | In

Backtracking, Easy

Quesion

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.

1
2
3
4
5
6
7
8
9
Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
Input: S = "3z4"
Output: ["3z4", "3Z4"]
Input: S = "12345"
Output: ["12345"]

Note:

  • S will be a string with length at most 12.
  • S will consist only of letters or digits.

My Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<String> letterCasePermutation(String S) {
        ArrayList<String> res=new ArrayList<>(Arrays.asList(S));
        for(int i=S.length()-1;i>=0;i--){
            for(int j=0,size=res.size();j<size&&S.charAt(i)>'9';j++){
                char[] ch = res.get(j).toCharArray();
                ch[i] += ch[i]<'a'?'a'-'A':'A'-'a';
                res.add(String.valueOf(ch));
            }
        }
        return res;
    }
}

Running time: 10ms

Better Answer:

Be careful to check whether a character is a digit or a letter(lower case or upper case).
BFS Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<String> letterCasePermutation(String S) {
        if (S == null) {
            return new LinkedList<>();
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(S);
        
        for (int i = 0; i < S.length(); i++) {
            if (Character.isDigit(S.charAt(i))) continue;            
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                String cur = queue.poll();
                char[] chs = cur.toCharArray();
                
                chs[i] = Character.toUpperCase(chs[i]);
                queue.offer(String.valueOf(chs));
                
                chs[i] = Character.toLowerCase(chs[i]);
                queue.offer(String.valueOf(chs));
            }
        }
        
        return new LinkedList<>(queue);
    }
}

DFS Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<String> letterCasePermutation(String S) {
        if (S == null) {
            return new LinkedList<>();
        }
        
        List<String> res = new LinkedList<>();
        helper(S, res, 0);
        return res;
    }
    
    public void helper(String s, List<String> res, int pos) {
        if (pos == s.length()) {
            res.add(s);
            return;
        }
        if (s.charAt(pos) >= '0' && s.charAt(pos) <= '9') {
            helper(s, res, pos + 1);
            return;
        }
        
        char[] chs = s.toCharArray();
        chs[pos] = Character.toLowerCase(chs[pos]);
        helper(String.valueOf(chs), res, pos + 1);
        
        chs[pos] = Character.toUpperCase(chs[pos]);
        helper(String.valueOf(chs), res, pos + 1);
    }
}

String to char[]

char[] array= str.toCharArray();

1
2
public char[] toCharArray()   
Return : It returns a newly allocated character array.

Char[] to String

String str = new String(ch);

String str2 = String.valueOf(ch);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class CharArrayToString
{
   public static void main(String args[])
   {
      // Method 1: Using String object
      char[] ch = {'g', 'o', 'o', 'd', ' ', 'm', 'o', 'r', 'n', 'i', 'n', 'g'};
      String str = new String(ch);
      System.out.println(str);
 
      // Method 2: Using valueOf method
      String str2 = String.valueOf(ch);
      System.out.println(str2);
   }
}

String to ArrayList

1
2
List<String> al = new ArrayList<String>();
al = Arrays.asList(str);

ASCII

1
2
3
4
5
6
'0' -- 48
'9' -- 57
'A' -- 65
'Z' -- 90
'a' -- 97
'z' -- 122

Use Queue~

1
Queue q1 = new LinkedList();

boolean add(E e): This method adds the specified element at the end of Queue. Returns true if the the element is added successfully or false if the element is not added that basically happens when the Queue is at its max capacity and cannot take any more elements.

E element(): This method returns the head (the first element) of the Queue.

boolean offer(object): This is same as add() method.

E remove(): This method removes the head(first element) of the Queue and returns its value.

E poll(): This method is almost same as remove() method. The only difference between poll() and remove() is that poll() method returns null if the Queue is empty.

E peek(): This method is almost same as element() method. The only difference between peek() and element() is that peek() method returns null if the Queue is empty.

Use Stack~