leetcode-784-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.

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

分析

回溯+递归，代码结构类似于 Permutation。

解决方案1(Java)

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

相关问题

题目来源