【剑指 Offer_38】字符串的排列_Java_深度优先搜索解法-白红宇

【剑指 Offer_38】字符串的排列_Java_深度优先搜索解法

阅读量：684 次

发布时间：2019-03-17

本文共 1177 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要生成一个字符串的所有排列，并确保排列中没有重复的元素。我们将使用深度优先搜索（DFS）来实现这一点，同时通过剪枝来处理重复字符，避免生成重复的排列。

方法思路

排列生成：使用DFS来生成所有可能的排列。对于每个位置，我们尝试固定一个字符，然后递归处理下一个位置。

剪枝处理重复字符：在递归过程中，使用一个集合记录已经固定在当前位置的字符。如果遇到重复字符，直接跳过，避免重复排列。

交换字符：在递归过程中交换当前字符位置上的字符，生成新的排列，并在递归返回时还原交换的结果。

解决代码

class Solution:    list = []    c = None    def permutation(self, s):        self.list = []        self.c = s.toCharArray()        self.dfs(0)        return list    def dfs(self, x):        if x == len(self.c) - 1:            self.list.add(strjoin(self.c))            return        set = set()        for i in range(x, len(self.c)):            if self.set.contains(self.c[i]):                continue            self.set.add(self.c[i])            self.swap(i, x)            self.dfs(x + 1)            self.swap(i, x)            self.set.remove(self.c[i])    def swap(self, i, x):        temp = self.c[i]        self.c[i] = self.c[x]        self.c[x] = temp

代码解释

初始化：将字符串转换为字符数组，并初始化结果列表为空。

递归函数dfs：

当前位置已处理完毕时，将当前字符数组转换为字符串并添加到结果列表。

使用循环遍历当前位置和之后的位置。

检查当前字符是否已经被使用过，如果被使用，跳过。

将字符交换到当前位置，进入下一层递归。

返回时还原交换，以保持原数组状态。

交换函数swap：交换两个位置上的字符，并还原交换的结果。

这个方法通过DFS生成所有排列，并通过剪枝处理重复字符，确保生成的排列唯一且符合要求。复杂度方面，时间复杂度在最坏情况下为O(n!)，其中n为字符串长度。

转载地址：http://qlzhz.baihongyu.com/

你可能感兴趣的文章