每日一道算法题 面试题 08.08. 有重复字符串的排列组合

题目

面试题 08.08. 有重复字符串的排列组合 - 力扣（LeetCode）

Python

class Solution:def permutation(self, S: str) -> List[str]:# 以索引记录字符是否用过le=len(S)idx=[_ for _ in range(le) ]# 组合得到的字符串combine=['']*leans=[]# 递归def fun(pos,choice):"""pos:索引,层数choice:可以选择的索引,choice使用集合，因为可以用减法"""if pos==le and (''.join(combine) not in ans):# 当pos=le-1时，combine[pos]还没写字符，故结束条件不为pos==le-1ans.append(''.join(combine))return # 归# 递for _ in list(choice):combine[pos]=S[_] # 当前层，即pos层fun(pos+1,choice-{_})  #下一层，即pos+1层fun(0,set(idx))return ans

C++

交换字符串元素求不同全排列

若字符串长度为n，将第一个字母分别与后面每一个字母进行交换，生成n种不同的全排列；再用第二个元素与后面每一个元素进行交换，生成n - 1种不同的全排列。

对于此题需要用一个Set集合来存放已经交换过的重复元素。

class Solution {
public:void dfs(vector<string>& ans,string& s,int idx){if(idx==s.size()){ans.push_back(s);return ;}set<char> record;for (int i=idx;i<s.size();i++){if(record.find(s[i])==record.end())  //集合里没有此字符{record.insert(s[i]);  //记录字符swap(s[idx],s[i]);  //交换dfs(ans,s,idx+1);swap(s[i],s[idx]);  //又换回来，复原}}}vector<string> permutation(string S) {vector<string> ans;dfs(ans,S,0);return ans;}
};

C语言

/*** Note: The returned array must be malloced, assume caller calls free().*/#include <string.h>void swap(char *a,char *b){char t;t=*a;*a =*b;*b=t;}int dfs(char *tmp,int len,int idx,char **ans,int *returnSize)
{char used_char[27]; //使用过的字母，26个字母+'\0'=27int j;int usedi=0;if(idx>=len-1){strcpy(ans[(*returnSize)++],tmp);return 0;}for(int i=idx;i<len;i++){if(usedi==0) used_char[usedi++]=tmp[i];else{for(j=0;j<usedi;j++) if(used_char[j]==tmp[i]) break;if(j>=usedi) used_char[usedi++]=tmp[i];else continue;}swap(&tmp[i],&tmp[idx]);dfs(tmp,len,idx+1,ans,returnSize);swap(&tmp[i],&tmp[idx]);}return 0;
}char** permutation(char* S, int* returnSize)
{char **ans,*tmp;int len=strlen(S);int i;int idx;//p_num为排列组合的总数tmp=(char *)malloc(sizeof(char)*(len+2));strcpy(tmp,S);ans=(char **)malloc(sizeof(char *)*1000);for( i=0;i<1000;i++){ans[i]=(char*)malloc(sizeof(char)*(len+1));}idx=0;*returnSize=0;dfs(tmp,len,idx,ans,returnSize);return ans;
}