剑指offer28 字符串的排列

1.全局变量可以在最后去定义并初始化，不一定非要在开头

2.此题有一种特殊情况需要考虑，比如字符串是“aa”，那输出应该是“aa”，而不是“aa，aa”，即相同的不输出。实现这个处理用了c++中的容器set，set不保存重复元素。在存储的时候，遇到相同的元素，set不会把相同的元素保存进set。clear是清空set中的元素。

3.迭代器的使用

class Solution {

public:

    vector<string> Permutation(string str) {

        if(str.size() == )

            return ans;

        length = str.size();

        int begin = ;

        Permutation(str,begin);

        //res.clear();

        set<string>::iterator it;

        for (it = res.begin(); it != res.end(); ++it)

            ans.push_back(*it);

        return ans;

    }

    void Permutation(string str,int begin){

        if(begin == length){

            res.insert(str);//insert可以直接加str的！不是只有迭代器！

            return;

        }

        for(int i = begin;i < length;i++){

            swap(str[begin],str[i]);

            Permutation(str,begin+);

            swap(str[begin],str[i]);

        }

    }

    set<string> res;

    vector<string> ans;

    int length = ;

};

一种典型错误：

class Solution {

public:

    vector<string> Permutation(string str) {

        if(str.size() == )

            return ans;

        int length = str.size();

        int begin = ;

        Permutation(str,begin);

        //res.clear();

        set<string>::iterator it;

        for (it = res.begin(); it != res.end(); ++it)

            ans.push_back(*it);

        return ans;

    }

    void Permutation(string str,int begin){

        if(begin == length){

            res.insert(str);

            return;

        }

        for(int i = begin;i < length;i++){

            swap(str[begin],str[i]);

            Permutation(str,begin+);

            swap(str[begin],str[i]);

        }

    }

    set<string> res;

    vector<string> ans;

};

正确代码中的length是一个全局变量，这里在Permutation(string str,int begin)中没有定义length，如果想在Permutation(string str,int begin)中使用Permutation(string str)的length，就必须把参数传进函数

中，即Permutation(string str,int begin，int length)。

思路错误的一种方法：

class Solution {

public:

    vector<string> Permutation(string str) {

        vector<string> result;

        set<string> ans;

        set<string>::iterator it

        int length = str.length();

        if(length <= )

            return result;

        for(int i = ;i < length;i++){

            for(int j = i;j < length;j++){

                char tmp = str[j];

                str[j] = str[i];

                str[i] = tmp;

                ans.insert(str);

                char tmp1 = str[j];

                str[j] = str[i];

                str[i] = tmp1;

            }

        }

        for(it = ans.begin();it != ans.end();it++){

            result.push_back(*it);

        }

        return result;

    }

};

这种思路的错误，以abc为例，只能得到abc、bac、cba、acb，但没有考虑到以b开头的bca和以c开头的cab

这个思路很好反应递归和普通一个循环的区别。

从思路的角度，把一个字符串分为前后两部分，比如a bcd，分别拿a与bcd去交换，然后固定第一个位置，再去找bcd的字符串排列。剑指offer上对整个思路讲解的很好，实现这个思路用递归来实现，而不是普通的循环。

巴特西

剑指offer28 字符串的排列

最新文章

热门文章