题目大意:给你一个字符串,每个字母可以变成大写也可以变成小写。让你输出所有可能字符串。
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 at most12
.S
will consist only of letters or digits.
Solution 1: DFS
Time complexity: O(n*2^l), l = # of letters in the string
Space complexity: O(n) + O(n*2^l)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 7 ms class Solution { public: vector<string> letterCasePermutation(string S) { vector<string> ans; dfs(S, 0, ans); return ans; } private: void dfs(string& S, int s, vector<string>& ans) { if (s == S.length()) { ans.push_back(S); return; } dfs(S, s + 1, ans); if (!isalpha(S[s])) return; S[s] ^= (1 << 5); dfs(S, s + 1, ans); S[s] ^= (1 << 5); } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 8 ms class Solution { public List<String> letterCasePermutation(String S) { List<String> ans = new ArrayList<>(); dfs(S.toCharArray(), 0, ans); return ans; } private void dfs(char[] S, int i, List<String> ans) { if (i == S.length) { ans.add(new String(S)); return; } dfs(S, i + 1, ans); if (!Character.isLetter(S[i])) return; S[i] ^= 1 << 5; dfs(S, i + 1, ans); S[i] ^= 1 << 5; } } |
Python 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
""" Author: Huahua Running time: 92 ms """ class Solution: def letterCasePermutation(self, S): ans = [] def dfs(S, i, n): if i == n: ans.append(''.join(S)) return dfs(S, i + 1, n) if not S[i].isalpha(): return S[i] = chr(ord(S[i]) ^ (1<<5)) dfs(S, i + 1, n) S[i] = chr(ord(S[i]) ^ (1<<5)) dfs(list(S), 0, len(S)) return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment