784. Letter Case Permutation 发表于 2022-09-25 Bit1234567891011121314151617181920212223242526272829303132333435363738class Solution { private static final int DIFF = 'a' - 'A'; public List<String> letterCasePermutation(String s) { List<String> resultList = new ArrayList<>(); for (int mask = 0; mask < 1 << s.length(); mask++) { char[] chars = s.toCharArray(); boolean duplicate = false; for (int i = 0; i < chars.length; i++) { // 注意数字不能翻转 if (Character.isDigit(chars[i]) && ((mask >> i) & 1) == 1) { duplicate = true; break; } if (((mask >> i) & 1)== 1) { chars[i] = flip(chars[i]); } } if (!duplicate) { resultList.add(new String(chars)); } } return resultList; } private char flip(char c) { if (c >= 'a') { return (char) (c - DIFF); } else { return (char) (c + DIFF); } }} Bit123456789101112131415161718192021222324252627282930class Solution { public List<String> letterCasePermutation(String s) { List<String> resultList = new ArrayList<>(); int letterCount = 0; for (int i = 0; i < s.length(); i++) { if (!Character.isDigit(s.charAt(i))) { letterCount++; } } for (int mask = 0; mask < 1 << letterCount; mask++) { char[] chars = s.toCharArray(); int letterOffset = 0; for (int i = 0; i < chars.length; i++) { if (!Character.isDigit(chars[i])) { if (((mask >> letterOffset) & 1) == 0) { // 注意此时要移动 letterOffset chars[i] = Character.toLowerCase(chars[i]); } else { chars[i] = Character.toUpperCase(chars[i]); } letterOffset++; } } resultList.add(new String(chars)); } return resultList; }} DFS123456789101112131415161718192021222324252627282930class Solution { public List<String> letterCasePermutation(String s) { List<String> resultList = new ArrayList<>(); StringBuilder sb = new StringBuilder(); dfs(resultList, sb, s, 0); return resultList; } private void dfs(List<String> resultList, StringBuilder sb, String s, int i) { if (i == s.length()) { resultList.add(sb.toString()); return; } char c = s.charAt(i); if (Character.isDigit(c)) { sb.append(c); dfs(resultList, sb, s, i + 1); sb.deleteCharAt(sb.length() - 1); } else { sb.append(Character.toLowerCase(c)); dfs(resultList, sb, s, i + 1); sb.deleteCharAt(sb.length() - 1); sb.append(Character.toUpperCase(c)); dfs(resultList, sb, s, i + 1); sb.deleteCharAt(sb.length() - 1); } }} DFS123456789101112131415161718192021class Solution { public List<String> letterCasePermutation(String s) { List<String> resultList = new ArrayList<>(); dfs(resultList, s.toCharArray(), 0); return resultList; } private void dfs(List<String> resultList,char[] chars, int i) { if (i == chars.length) { resultList.add(new String(chars)); return; } dfs(resultList, chars, i + 1); // not flip if (Character.isLetter(chars[i])) { // flip chars[i] ^= ' '; dfs(resultList, chars, i + 1); } }} Reference784. Letter Case Permutation