Leetcode
Backtracking
Bit Manipulation
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.
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 between 1 and 12.
- S will consist only of letters or digits.
分析¶
使用回溯法:
public List<String> letterCasePermutation(String S) { List<String> list = new ArrayList<>(); if (S == null) return list; letterCasePermutation(list, new StringBuilder(), S, 0); return list; } private void letterCasePermutation(List<String> list, StringBuilder sb, String S, int index){ // base case if (index == S.length()) {list.add(sb.toString()); return;} // chosen char c = S.charAt(index); if (!Character.isLetter(c)) { // numbers sb.append(c); letterCasePermutation(list, sb, S, index + 1); // explore sb.deleteCharAt(sb.length() - 1); // unchosen } else { sb.append(Character.toLowerCase(c)); letterCasePermutation(list, sb, S, index + 1); sb.deleteCharAt(sb.length() - 1); sb.append(Character.toUpperCase(c)); letterCasePermutation(list, sb, S, index + 1); sb.deleteCharAt(sb.length() - 1); } }
近期评论