784.Letter-Case-Permutation

784. Letter Case Permutation

题目地址

https://leetcode.com/problems/letter-case-permutation/

题目描述

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 = "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 between 1 and 12.
S will consist only of letters or digits.

代码

Approach #1 Recursion

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;
  }
}

Approach #2 Binary Mask

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

    List<String> ans = new ArrayList();

    for (int bits = 0; bits < 1 << count; 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);
        }
      }
    }

    return ans;
  }
}