784. Letter Case Permutation - Medium
문제
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.
제한사항
- S will be a string with length between 1 and 12.
- S will consist only of letters or digits.
입출력 예
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"]
풀이
- Recursive, BackTracking
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
class Solution {
public:
void backTracking(std::string S, int index, std::vector<std::string>& items) {
// index가 문자열만큼 커지면 리턴
if (index >= S.size()) {
items.push_back(S);
return;
}
backTracking(S, index + 1, items);
// 현재 문자가 소문자일때 대문자로 바꿔 현재까지의 문자열에 저장
// 현재 문자가 대문자일때 소문자로 바꿔 현재까지의 문자열에 저장
if ('a' <= S[index] && S[index] <= 'z') {
S[index] -= 32;
backTracking(S, index + 1, items);
} else if ('A' <= S[index] && S[index] <= 'Z') {
S[index] += 32;
backTracking(S, index + 1, items);
}
}
vector<string> letterCasePermutation(string S) {
std::vector<std::string> res;
backTracking(S, 0, res);
return res;
}
};