劍指offer之字符串的全排列

1 問題

求字符串的全排列，比如字符串a(chǎn)bc，它的全排列如下

abc, acb, bac, bca, cad, cba

 
2 思路

我們先固定第一個字符，這里的第一個字符肯定是這個字符串里面字符串的全子集（不包含重復），abc字符串，我們a和a交換，這里也就是固定a字符的，然后我們只需要求出后面bc字符的全排列，這個時候我們可以用遞歸，我們依然b和b進行交換，c和c進行交換，到了末尾我們遞歸就結束，記得return.我們可以得出bc全排列的一種既bc,然后我們b和c需要交換位置，變成了cb,然后我們b和b進行了一次交換，然后我們可以得到bc全排列的一種既cb,所以固定a字符，我們可以得到全排列字符串a(chǎn)bc acb,所以依次類推，我們可以固定b字符和c字符求出所以字符串的全排列

 
3 代碼實現(xiàn)

c++版本

    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
     
    using namespace std;
     
    class Permutation{
    private:
        void permutation(string str, int begin);
    public:
        vector<string> permutation(string str);
        vector<string> result;
    };
     
    vector<string> Permutation::permutation(string str)
    {
        if (str.length() == 0)
        {
        return result;
        }
        permutation(str, 0);
        sort(result.begin(), result.end());   
        return result;
    }
     
    void Permutation::permutation(string str, int begin)
    {
        if (begin == str.length())
        {
        result.push_back(str);
         return;
        }
        for (int i = begin; i < str.length(); ++i)
        {
        if (i != begin && str[i] == str[begin])
                continue;
        //這里開始交換第一個元素和后面的元素，也就是起到固定的作用
            swap(str[begin], str[i]);
        //遞歸后面的子字符串
            permutation(str, begin + 1);
        //交換了要記得還原
        swap(str[i], str[begin]);
       }
    }
     
    int main()
    {
        Permutation h;
        h.permutation("abc");
        vector<string> result = h.result;
        for(int i = 0; i < result.size(); ++i)
        {
            std::cout << result[i] << std::endl;   
        }
        return 0;
    }

c版本

    #include <stdio.h>
     
    void permutation(char *str);
    void permutation_core(char *str, char *begin);
     
    void permutation(char *str)
    {
        if (str == NULL)
        {
            printf("str is NULL\n");
            return;
        }
        permutation_core(str, str);
    }
     
    void permutation_core(char *str, char *begin)
    {
       if (*begin == '\0')
       {
           printf("%s\n", str);
       }
       else
       {
            for (char *ch = begin; *ch != '\0'; ++ch)
            {
                char temp = *ch;
                *ch = *begin;
                *begin = temp;
                permutation_core(str, begin + 1);
                temp = *ch;
                *ch = *begin;
                *begin = temp;
     
            }
       }
    }
    int main()
    {
        //這里不能用char *str = "adc",因為我們需要交換字符串里面的字符，需要操作棧內存
        char str[] = "abc";  
        permutation(str);
        return 0;
    }

這樣寫，如果有重復的字符就有問題，比如ada,我們優(yōu)化如下，去掉重

    #include <stdio.h>
    #include <string.h>
     
    void permutation(char *str);
    void swap(char *str, int start, int end);
    void permutation_core(char *str, int begin, int end);
     
    void permutation(char *str)
    {
        if (str == NULL)
        {
            printf("str is NULL\n");
            return;
        }
        int len = strlen(str);
        printf("len is %d\n", len);
        permutation_core(str, 0, len);
    }
     
    void permutation_core(char *str, int begin, int end)
    {
        if (begin == end)
        {
            printf("%s\n", str);
        }
        else
        {
            for (int i = begin; i < end; ++i)
            {
                if (i != begin && str[i] == str[begin])
                    continue;
                swap(str, i, begin);
                permutation_core(str, begin + 1, end);   
                swap(str, i, begin);
            }
           
        }
       
    }
     
     
    void swap(char str[], int start, int end)
    {
            char ch = str[start];
            str[start] = str[end];
            str[end] =  ch;
    }
     
    int main()
    {
        //這里不能用char *str = "adc",因為我們需要交換字符串里面的字符，需要操作棧內存
        char str[] = "abc";  
        permutation(str);
        return 0;
    }


 
4 運行結果

c++版本運行結果

    abc
    acb
    bac
    bca
    cab
    cba

c版本運行結果

    abc
    acb
    bac
    bca
    cba
    cab

 



 


作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎入門進階人工智能(鏈接)