打印一個(gè)字符串的全部排列

自負(fù)串全排序:
舉例:
abc 的全排序是:
abc
acb
bac
bca
cba
cab

解題思路

因?yàn)槊總€(gè)字符都要選,其實(shí)就是選擇每個(gè)字符的順序,那我們遞歸時(shí),就可以把不同順序一直遞歸下去.

代碼演示

    /**
     * 字符串的全排列
     * @param str
     * @return
     */
    public static List<String> allSubSequence(String str){
        if (str == null || str.equals("")){
            return null;
        }
        //保存答案
        ArrayList<String> ans = new ArrayList<>();
        process(str.toCharArray(),0,ans);
        return ans;
    }

    /**
     * 遞歸
     * @param str 字符串?dāng)?shù)組
     * @param index  下標(biāo)值
     * @param ans 保存答案
     */
    public static void process(char[]str, int index, List<String> ans){
        //base case
        if (index == str.length){
            ans.add(String.valueOf(str));
        }else{
            for (int i = index;i < str.length;i++){
                //因?yàn)槊總€(gè)字符都要選,我們只是選擇順序,因此交換下順序,
                swap(str,i, index);
                //然后遞歸
                process(str,index + 1,ans);
                //要把交換過的順序 恢復(fù)回去,這樣才能保證遞歸出全部順序.
                swap(str,i,index);
            }
        }
    }

打印一個(gè)字符串的全部排列，要求不要出現(xiàn)重復(fù)的排列

解題思路:
我們可以按上面的代碼去做,只需要用HashSet 去保存答案,就會(huì)去重了,但這樣并沒有優(yōu)化效率,在遞歸時(shí)去掉可能會(huì)重復(fù)的值,這樣才能把效率優(yōu)化下來,
怎樣優(yōu)化呢:
兩個(gè)相同的字符,如果已經(jīng)有一個(gè)出現(xiàn)過在某個(gè)位置,那么剩下相同的字符也不用重復(fù)交換了,這樣會(huì)提高效率
根據(jù)上面的思路,我們只需要加個(gè)判斷,
因?yàn)樽址D(zhuǎn)換成數(shù)字的值在0-255 ,因此用長(zhǎng)度256 的數(shù)組就可以標(biāo)記了,代碼演示,

代碼演示,

    /**
     * 打印一個(gè)字符串的全部排列，要求不要出現(xiàn)重復(fù)的排列
     * @param str
     * @return
     */
    public static List<String> allSubSequence2(String str){
        if (str == null || str.equals("")){
            return null;
        }
        ArrayList<String> ans = new ArrayList<>();
        process2(str.toCharArray(),0,ans);
        return ans;
    }

    /**
     * 遞歸
     * @param str
     * @param index
     * @param ans
     */
    public static void process2(char[]str, int index, List<String> ans){
        if (index == str.length){
            ans.add(String.valueOf(str));
        }else{
            //標(biāo)記相同的字符是否交換過,
            boolean[] flag = new boolean[256];
            for (int i = index;i < str.length;i++){
                if (!flag[str[i]]){
                    flag[str[i]] = true;
                    swap(str,i, index);
                    process(str,index + 1,ans);
                    swap(str,i,index);
                }

            }
        }
    }

遞歸專題

遞歸–字符串的全部子序列和不重復(fù)的子序列（java）

遞歸–漢諾塔問題(java)文章來源地址http://www.zghlxwxcb.cn/news/detail-461974.html

到了這里，關(guān)于遞歸--打印一個(gè)字符串的全部排列(java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！