代理建設(shè)網(wǎng)站,wordpress 七牛 上傳,360做網(wǎng)站多少錢一年,網(wǎng)站開發(fā)過(guò)程及要點(diǎn)字母大小寫全排列 問(wèn)題描述 給定一個(gè)字符串 s#xff0c;通過(guò)將字符串中的每個(gè)字母改成大寫或小寫#xff0c;生成所有可能的字符串。 返回所有可能的字符串組成的列表。數(shù)字和特殊字符保持不變。 示例#xff1a; 輸入: s a1b2 輸出: [a1b2,…字母大小寫全排列問(wèn)題描述給定一個(gè)字符串s通過(guò)將字符串中的每個(gè)字母改成大寫或小寫生成所有可能的字符串。返回所有可能的字符串組成的列表。數(shù)字和特殊字符保持不變。示例輸入: s a1b2 輸出: [a1b2, a1B2, A1b2, A1B2] 輸入: s 3z4 輸出: [3z4, 3Z4] 輸入: s 12345 輸出: [12345]算法思路核心字符只有字母需要考慮大小寫變化數(shù)字和特殊字符保持不變選擇每個(gè)字母有2種選擇大寫或小寫如果有k個(gè)字母總共有2^k種排列方法回溯遞歸處理每個(gè)位置遇到字母時(shí)嘗試兩種大小寫迭代從空結(jié)果開始逐個(gè)字符擴(kuò)展所有可能的結(jié)果位運(yùn)算用二進(jìn)制位表示每個(gè)字母的選擇0小寫1大寫代碼實(shí)現(xiàn)方法一回溯importjava.util.*;classSolution{/** * 使用回溯生成字母大小寫全排列 * * param s 輸入字符串 * return 所有可能的字符串列表 */publicListStringletterCasePermutation(Strings){ListStringresultnewArrayList();// 將字符串轉(zhuǎn)換為字符數(shù)組char[]charss.toCharArray();// 從索引0開始回溯backtrack(chars,0,result);returnresult;}/** * 回溯函數(shù)遞歸生成所有可能的排列 * * param chars 當(dāng)前字符數(shù)組 * param index 當(dāng)前處理的字符索引 * param result 結(jié)果列表 */privatevoidbacktrack(char[]chars,intindex,ListStringresult){// 遞歸終止條件處理完所有字符if(indexchars.length){result.add(newString(chars));return;}charcurrentchars[index];if(Character.isLetter(current)){// 1保持小寫或原樣chars[index]Character.toLowerCase(current);backtrack(chars,index1,result);// 2轉(zhuǎn)換為大寫chars[index]Character.toUpperCase(current);backtrack(chars,index1,result);}else{// 非字母字符直接跳過(guò)backtrack(chars,index1,result);}}}方法二迭代importjava.util.*;classSolution{/** * 使用迭代生成字母大小寫全排列 * * param s 輸入字符串 * return 所有可能的字符串列表 */publicListStringletterCasePermutation(Strings){ListStringresultnewArrayList();result.add();// 初始化為空字符串// 逐個(gè)字符處理for(charc:s.toCharArray()){ListStringnewResultnewArrayList();// 對(duì)當(dāng)前結(jié)果中的每個(gè)字符串?dāng)U展新的字符for(Stringstr:result){if(Character.isLetter(c)){// 字母添加小寫和大寫兩種情況newResult.add(strCharacter.toLowerCase(c));newResult.add(strCharacter.toUpperCase(c));}else{// 非字母直接添加newResult.add(strc);}}resultnewResult;}returnresult;}}方法三位運(yùn)算importjava.util.*;classSolution{/** * 使用位運(yùn)算生成字母大小寫全排列 * * param s 輸入字符串 * return 所有可能的字符串列表 */publicListStringletterCasePermutation(Strings){// 首先找出所有字母的位置ListIntegerletterIndicesnewArrayList();char[]charss.toCharArray();for(inti0;ichars.length;i){if(Character.isLetter(chars[i])){letterIndices.add(i);}}intletterCountletterIndices.size();ListStringresultnewArrayList();// 枚舉所有可能的位組合 (0 到 2^letterCount - 1)for(intmask0;mask(1letterCount);mask){char[]currentArrays.copyOf(chars,chars.length);// 根據(jù)mask的每一位決定對(duì)應(yīng)字母的大小寫for(inti0;iletterCount;i){if((mask(1i))!0){// 第i位為1大寫current[letterIndices.get(i)]Character.toUpperCase(current[letterIndices.get(i)]);}else{// 第i位為0小寫current[letterIndices.get(i)]Character.toLowerCase(current[letterIndices.get(i)]);}}result.add(newString(current));}returnresult;}}算法分析時(shí)間復(fù)雜度O(2^n × m)n 字符串中字母的個(gè)數(shù)m 字符串總長(zhǎng)度共有2^n種排列每種排列需要O(m)時(shí)間構(gòu)建空間復(fù)雜度回溯O(m) - 遞歸深度為m不包括結(jié)果存儲(chǔ)迭代O(2^n × m) - 需要存儲(chǔ)所有中間結(jié)果位運(yùn)算O(2^n × m) - 需要存儲(chǔ)所有結(jié)果算法過(guò)程s “a1b2”回溯開始: index0, chars[a,1,b,2] ├─ index0, a是字母 │ ├─ 小寫: chars[a,1,b,2], index1 │ │ ├─ index1, 1不是字母 → index2 │ │ │ ├─ index2, b是字母 │ │ │ │ ├─ 小寫: chars[a,1,b,2], index3 │ │ │ │ │ └─ index3, 2不是字母 → index4 → 添加a1b2 │ │ │ │ └─ 大寫: chars[a,1,B,2], index3 │ │ │ │ └─ index3, 2不是字母 → index4 → 添加a1B2 │ │ └─ 大寫: chars[A,1,b,2], index1 │ ├─ index1, 1不是字母 → index2 │ │ ├─ index2, b是字母 │ │ │ ├─ 小寫: chars[A,1,b,2], index3 → 添加A1b2 │ │ │ └─ 大寫: chars[A,1,B,2], index3 → 添加A1B2最終結(jié)果[“a1b2”, “a1B2”, “A1b2”, “A1B2”]迭代初始[“”]處理’a’[“a”, “A”]處理’1’[“a1”, “A1”]處理’b’[“a1b”, “a1B”, “A1b”, “A1B”]處理’2’[“a1b2”, “a1B2”, “A1b2”, “A1B2”]測(cè)試用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 測(cè)試用例1標(biāo)準(zhǔn)示例System.out.println(Test 1: solution.letterCasePermutation(a1b2));// [a1b2, a1B2, A1b2, A1B2]// 測(cè)試用例2包含數(shù)字System.out.println(Test 2: solution.letterCasePermutation(3z4));// [3z4, 3Z4]// 測(cè)試用例3純數(shù)字System.out.println(Test 3: solution.letterCasePermutation(12345));// [12345]// 測(cè)試用例4單個(gè)字母System.out.println(Test 4: solution.letterCasePermutation(a));// [a, A]// 測(cè)試用例5空字符串System.out.println(Test 5: solution.letterCasePermutation());// []// 測(cè)試用例6多個(gè)連續(xù)字母System.out.println(Test 6: solution.letterCasePermutation(ab));// [ab, aB, Ab, AB]// 測(cè)試用例7包含大寫字母的輸入System.out.println(Test 7: solution.letterCasePermutation(A1B2));// [a1b2, a1B2, A1b2, A1B2]// 測(cè)試用例8混合大小寫和特殊字符System.out.println(Test 8: solution.letterCasePermutation(C1d));// [c1d, c1D, C1d, C1D]// 測(cè)試用例9較長(zhǎng)字符串System.out.println(Test 9: solution.letterCasePermutation(a1b2c3));// 8種組合// 測(cè)試用例10只有特殊字符System.out.println(Test 10: solution.letterCasePermutation(!#$%));// [!#$%]}關(guān)鍵點(diǎn)字符使用Character.isLetter()準(zhǔn)確判斷字母包含所有Unicode字母不僅僅是a-z和A-Z大小寫轉(zhuǎn)換使用Character.toLowerCase()和Character.toUpperCase()回溯修改字符數(shù)組時(shí)要注意狀態(tài)恢復(fù)邊界情況空字符串、純數(shù)字、純字母等特殊情況常見問(wèn)題為什么回溯空間復(fù)雜度更低回溯只在遞歸棧中存儲(chǔ)當(dāng)前路徑迭代需要存儲(chǔ)所有中間結(jié)果空間開銷大