题目

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:

  1. Input: S = "a1b2"
  2. Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

  1. Input: S = "3z4"
  2. Output: ["3z4","3Z4"]

Example 3:

  1. Input: S = "12345"
  2. Output: ["12345"]

Example 4:

  1. Input: S = "0"
  2. Output: ["0"]

Constraints:

  • S will be a string with length between 1 and 12.
  • S will consist only of letters or digits.

题意

给定一个字符串，其中的字母可以互换大小写，求所有可能的组合。

思路

DFS。

代码实现

Java

  1. class Solution {
  2.     public List<String> letterCasePermutation(String S) {
  3.         List<String> ans = new ArrayList<>();
  4.         dfs(S, 0, "", ans);
  5.         return ans;
  6.     }
  8.     private void dfs(String S, int index, String cur,  List<String> ans) {
  9.         if (index == S.length()){
  10.             ans.add(cur);
  11.             return; 
  12.         }
  14.         char c = S.charAt(index);
  15.         if (Character.isDigit(c)) {
  16.             dfs(S, index + 1, cur + c, ans);
  17.         } else {
  18.             dfs(S, index + 1, cur + Character.toUpperCase(c), ans);
  19.             dfs(S, index + 1, cur + Character.toLowerCase(c), ans);
  20.         }
  21.     }
  22. }