Welcome to Subscribe On Youtube
784. Letter Case Permutation
Description
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. Return the output in any order.
Example 1:
Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"]
Example 2:
Input: s = "3z4" Output: ["3z4","3Z4"]
Constraints:
1 <= s.length <= 12sconsists of lowercase English letters, uppercase English letters, and digits.
Solutions
DFS.
-
class Solution { private List<String> ans = new ArrayList<>(); private char[] t; public List<String> letterCasePermutation(String s) { t = s.toCharArray(); dfs(0); return ans; } private void dfs(int i) { if (i >= t.length) { ans.add(String.valueOf(t)); return; } dfs(i + 1); if (t[i] >= 'A') { t[i] ^= 32; dfs(i + 1); } } } -
class Solution { public: vector<string> letterCasePermutation(string s) { vector<string> ans; function<void(int)> dfs = [&](int i) { if (i >= s.size()) { ans.emplace_back(s); return; } dfs(i + 1); if (s[i] >= 'A') { s[i] ^= 32; dfs(i + 1); } }; dfs(0); return ans; } }; -
class Solution: def letterCasePermutation(self, s: str) -> List[str]: def dfs(i): if i >= len(s): ans.append(''.join(t)) return dfs(i + 1) if t[i].isalpha(): t[i] = chr(ord(t[i]) ^ 32) dfs(i + 1) t = list(s) ans = [] dfs(0) return ans -
func letterCasePermutation(s string) (ans []string) { t := []byte(s) var dfs func(int) dfs = func(i int) { if i >= len(t) { ans = append(ans, string(t)) return } dfs(i + 1) if t[i] >= 'A' { t[i] ^= 32 dfs(i + 1) } } dfs(0) return ans } -
function letterCasePermutation(s: string): string[] { const n = s.length; const cs = [...s]; const res = []; const dfs = (i: number) => { if (i === n) { res.push(cs.join('')); return; } dfs(i + 1); if (cs[i] >= 'A') { cs[i] = String.fromCharCode(cs[i].charCodeAt(0) ^ 32); dfs(i + 1); } }; dfs(0); return res; } -
impl Solution { fn dfs(i: usize, cs: &mut Vec<char>, res: &mut Vec<String>) { if i == cs.len() { res.push(cs.iter().collect()); return; } Self::dfs(i + 1, cs, res); if cs[i] >= 'A' { cs[i] = char::from((cs[i] as u8) ^ 32); Self::dfs(i + 1, cs, res); } } pub fn letter_case_permutation(s: String) -> Vec<String> { let mut res = Vec::new(); let mut cs = s.chars().collect::<Vec<char>>(); Self::dfs(0, &mut cs, &mut res); res } }