【深度遍历】【排列组合】【力扣】有重复字符串的排列组合

目录

题目描述

解题思路

解答（C语言）

解答（python）

---

题目描述

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

示例2:

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

解题思路

排列组合用深度遍历即可获取全部情况

注意点：重复的组合出现一次即可，比如 [e, 第1个q, 第2个q] 和 [e, 第2个q, 第1个q] 为同一个排列组合

解答（C语言）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>char **result = NULL;  // 保存全部情况
int count = 0;  // 情况个数void Find(int pos, char *S, int isUsed[], char dest[], size_t sLen)
{// pos的含义：尝试从全部字母中取出一个字母放到排列组合的第pos个位置// 刚好组合完成if (pos == sLen) {// printf("%s\n", dest);// 保存结果count++;result = (char **)realloc(result, count * sizeof(char *));result[count - 1] = (char *)malloc(sLen + 1);strcpy(result[count - 1], dest);return;}// 从剩余的字母中取出一个字母for (int i = 0; i < sLen; i++) {// 已经被用来组合的字母不再使用if (isUsed[i] == 1) {continue;}// 两个相同字母出现一次即可if (i+1 < sLen && S[i] == S[i+1] && isUsed[i+1] == 1) {continue;}// 因为第i个字母未被使用，因此取出来放到排列组合的第pos个位置dest[pos] = S[i];// 第i个字母标记为已使用isUsed[i] = 1;// 对排列组合的第pos个位置的下一个位置找字母Find(pos + 1, S, isUsed, dest, sLen);// 排列组合的第pos个位置尝试过第i个字母// 现在不用第i个字母了，而是继续循环尝试第i+1个字母isUsed[i] = 0;}/* 循环结束时函数也会结束，说明在第pos这个深度处的全部遍历结束，在 pos - 1深度处的遍历中，对下一个字母的尝试将开始*/
}int CmpFunc(const void *a, const void *b)
{return *(char *)a - *(char *)b;
}/*** Note: The returned array must be malloced, assume caller calls free().*/
char **permutation(char *S, int *returnSize)
{count = 0;result = NULL;// 准备要用到的变量size_t sLen = strlen(S);char dest[sLen + 1];memset(dest, 0, sizeof(dest));int isUsed[sLen];memset(isUsed, 0, sizeof(isUsed));// 排序qsort(S, sLen, sizeof(char), CmpFunc);// 深度遍历Find(0, S, isUsed, dest, sLen);// 返回结果*returnSize = count;return result;
}int main() 
{int select = 1;if (select == 1) {char S[] = "qqe";int returnSize;permutation(S, &returnSize);} else if (select == 2) {char S[] = "ab";int returnSize;permutation(S, &returnSize);} return 0;
}

解答（python）

class Solution:def permutation(self, S: str) -> List[str]:data = list(S)data.sort()used = [False] * len(data)res = []def backtrack(content):if len(content) == len(data):res.append(content)returnfor i in range(len(data)):# 当前轮组合中已使用过不再使用if used[i]:continue# 使用过的相邻元素不再使用if i > 0 and data[i] == data[i-1] and not used[i-1]:continue# 将当前组合使用起来content += data[i]used[i] = True# 继续下一轮的取数backtrack(content)# 当组合取数完毕或者循环完毕，释放当前位置数的可使用状态used[i] = Falsecontent = content[:-1]   # 重新从该位置取数组合时，应当将content恢复到该位置时的状态               backtrack('')return res