題目描述
這是 LeetCode 上的 784. 字母大小寫全排列 ，難度為 中等。
Tag : 「DFS」、「爆搜」、「二進制枚舉」
給定一個字元串
s
，通過将字元串
s
中的每個字母轉變大小寫，我們可以獲得一個新的字元串。
傳回 所有可能得到的字元串集合 。以 任意順序 傳回輸出。
示例 1：
輸入：s = "a1b2"
輸出：["a1b2", "a1B2", "A1b2", "A1B2"] 示例 2:
輸入: s = "3z4"
輸出: ["3z4","3Z4"] 提示:
-
s
DFS
資料範圍為 ，同時要我們求所有具體方案，容易想到使用
DFS
進行「爆搜」。
我們可以從前往後考慮每個 ，根據
- 若
- 若
設計
DFS
函數為
void dfs(int idx, int n, String cur)
：其中 固定為具體方案的長度（即原字元串長度），而
idx
和
cur
分别為目前處理到哪一個 ，而
cur
則是目前具體方案。
根據上述分析可知，當 不為字母，将其直接追加到
cur
上，并決策下一個位置 ；而當 為字母時，我們可以選擇将 追加到
cur
上（保留原字母）或是将 進行翻轉後再追加到
cur
上（進行大小寫轉換）。
最後當我們滿足
idx = n
時，說明已經對原字元串的每一位置決策完成，将目前具體方案
cur
加入答案。
一些細節：我們可以通過與 32
Java 代碼：
class Solution {
char[] cs;
List<String> ans = new ArrayList<>();
public List<String> letterCasePermutation(String s) {
cs = s.toCharArray();
dfs(0, s.length(), new char[s.length()]);
return ans;
}
void dfs(int idx, int n, char[] cur) {
if (idx == n) {
ans.add(String.valueOf(cur));
return ;
}
cur[idx] = cs[idx];
dfs(idx + 1, n, cur);
if (Character.isLetter(cs[idx])) {
cur[idx] = (char) (cs[idx] ^ 32);
dfs(idx + 1, n, cur);
}
}
} TypeScript 代碼：
function letterCasePermutation(s: string): string[] {
const ans = new Array<string>()
function dfs(idx: number, n: number, cur: string): void {
if (idx == n) {
ans.push(cur)
return
}
dfs(idx + 1, n, cur + s[idx])
if ((s[idx] >= 'a' && s[idx] <= 'z') || (s[idx] >= 'A' && s[idx] <= 'Z')) {
dfs(idx + 1, n, cur + String.fromCharCode(s.charCodeAt(idx) ^ 32))
}
}
dfs(0, s.length, "")
return ans
} Python 代碼：
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
ans = []
def dfs(idx, n, cur):
if idx == n:
ans.append(cur)
return
dfs(idx + 1, n, cur + s[idx])
if 'a' <= s[idx] <= 'z' or 'A' <= s[idx] <= 'Z':
dfs(idx + 1, n, cur + s[idx].swapcase())
dfs(0, len(s), '')
return ans - 時間複雜度：最壞情況下原串
s
- 空間複雜度：
二進制枚舉
根據解法一可知，具體方案的個數與字元串
s1
存在的字母個數相關，當
s1
存在
m
個字母時，由于每個字母存在兩種決策，總的方案數個數為
是以可以使用「二進制枚舉」的方式來做：使用變量
s
代表字元串
s1
的字母翻轉狀态，
s
的取值範圍為
[0, 1 << m)
。若
s
的第 位為
0
代表在
s1
中第 個字母不進行翻轉，而當為
1
時則代表翻轉。
每一個狀态
s
對應了一個具體方案，通過枚舉所有翻轉狀态
s
，可構造出所有具體方案。
Java 代碼：
class Solution {
public List<String> letterCasePermutation(String str) {
List<String> ans = new ArrayList<String>();
int n = str.length(), m = 0;
for (int i = 0; i < n; i++) m += Character.isLetter(str.charAt(i)) ? 1 : 0;
for (int s = 0; s < (1 << m); s++) {
char[] cs = str.toCharArray();
for (int i = 0, j = 0; i < n; i++) {
if (!Character.isLetter(cs[i])) continue;
cs[i] = ((s >> j) & 1) == 1 ? (char) (cs[i] ^ 32) : cs[i];
j++;
}
ans.add(String.valueOf(cs));
}
return ans;
}
} TypeScript 代碼：
function letterCasePermutation(str: string): string[] {
function isLetter(ch: string): boolean {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
}
const ans = new Array<string>()
let n = str.length, m = 0
for (let i = 0; i < n; i++) m += isLetter(str[i]) ? 1 : 0
for (let s = 0; s < (1 << m); s++) {
let cur = ''
for (let i = 0, j = 0; i < n; i++) {
if (!isLetter(str[i]) || ((s >> j) & 1) == 0) cur += str[i]
else cur += String.fromCharCode(str.charCodeAt(i) ^ 32)
if (isLetter(str[i])) j++
}
ans.push(cur)
}
return ans
} Python 代碼：
class Solution:
def letterCasePermutation(self, s1: str) -> List[str]:
def isLetter(ch):
return 'a' <= ch <= 'z' or 'A' <= ch <= 'Z'
ans = []
n, m = len(s1), len([ch for ch in s1 if isLetter(ch)])
for s in range(1 << m):
cur = ''
j = 0
for i in range(n):
if not isLetter(s1[i]) or not ((s >> j) & 1):
cur += s1[i]
else:
cur += s1[i].swapcase()
if isLetter(s1[i]):
j += 1
ans.append(cur)
return ans - 時間複雜度：最壞情況下原串
s
- 空間複雜度：
最後
這是我們「刷穿 LeetCode」系列文章的第
No.784
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)