文章目錄

• 1 題目理解
• 2 回溯

1 題目理解

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. You can return the output in any order.
輸入：字符串
輸出：字符串可能的變形
規則：每一個位置上的字符都可能變為大寫或者小寫。非字母的保持原字母。

Example 1:

Input: S = “a1b2”
Output: [“a1b2”,“a1B2”,“A1b2”,“A1B2”]

2 回溯

每個字符位，可能是大寫，也可能是小寫。回溯遞歸即可實現。

class Solution {private String S;private List<String> answer;public List<String> letterCasePermutation(String S) {this.S = S;answer = new ArrayList<String>();dfs(0,"");return answer;}private void dfs(int index,String str){if(index >= S.length()){answer.add(str);}else{char ch = S.charAt(index);if(ch>='0' && ch<='9'){dfs(index+1,str+ch);}else if(ch>='A' && ch<='Z'){dfs(index+1,str+ch);ch += 32;dfs(index+1,str+ch);}else if(ch>='a' && ch<='z'){dfs(index+1,str+ch);ch -= 32;dfs(index+1,str+ch);}}} }

第二種方式：可以使用二進制位。對于每一位有兩種選擇的情況可以用二進制位來解決。

class Solution {public List<String> letterCasePermutation(String S) {int charCount = 0;for(char ch : S.toCharArray()){if(Character.isLetter(ch)){charCount++;}}List<String> answer = new ArrayList<String>();int max = (1<<charCount)-1;for(int i = 0;i<=max;i++){int j = 0;StringBuilder s = new StringBuilder();for(char ch : S.toCharArray()){if(Character.isLetter(ch)){if(((i>>j) &1)==1){s.append(Character.toLowerCase(ch));}else{s.append(Character.toUpperCase(ch));}j++;}else{s.append(ch);}}answer.add(s.toString());}return answer;} }

此處用StringBuilder比String快了不好。

總結

以上是生活随笔為你收集整理的784. Letter Case Permutation的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。