• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

剑指offer(38)

剑指 Offer 38. 字符串的排列

输入一个字符串并打印出该字符串中所有字符的排列。

您可以以任何顺序返回这个字符串数组,但是其中不能有重复的元素。

示例:

输入:s='abc '

输出:['ABC ',' ACB ',' BAC ',' BCA ',' CAB ',' CBA']

限制:

1=s的长度=8

用回溯法解决这个问题。

对于字符重复的问题,要学会字符串排序和处理。

类别解决方案{

公共:

矢量字符串记录;

矢量vis

//回溯方法

void回溯(const string s,int i,int n,string perm) {

if (i==n) {

rec . push _ back(perm);

返回;

}

//每次遍历字符串s时,选择未使用的那个

for(int j=0;j n;j ) {

//如果J的位置被选中或者左边有重复字符,但没有被选中,就不要选中(左边有重复字符,但那个字符没有被选中,说明已经被选中)

if (vis[j] || (j 0!vis[j-1]s[j-1]==s[j]){

继续;

}

vis[j]=true;

//做出选择

perm . push _ back(s[j]);

回溯(s,i 1,n,perm);

//取消选择

perm . pop _ back();

vis[j]=false;

}

}

向量字符串排列(字符串s) {

int n=s . size();

//vis是一个判别数组,用来判断这个位置的字符是否被使用。

vis . resize(n);

//排序,这样可以处理字符重复的问题。

sort(s.begin()、s . end());

串烫;

//回溯

回溯(s,0,n,perm);

返回记录;

}

};

Link to comment
Share on other sites