剑指offer-27、字符串的排列
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个字符串，按字典序打印出该字符串中字符的所有排列。例如输⼊字符串 abc ，则按字典序打印出由字符 a , b , c 所能排列出来的所有字符串 abc , acb , bac , bca , cab 和 cba 。</p>
<p>输⼊描述：输⼊⼀个字符串，⻓度不超过9(可能有字符重复)，字符只包括⼤⼩写字⺟</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="递归回溯使用set去重">递归回溯（使用Set去重）</h3>
<p>看到题目，应该就知道要使⽤回溯了。</p>
<p>通过 <strong>回溯算法</strong> 生成所有排列，配合 <strong>剪枝条件</strong> 实现去重和字典序输出。关键步骤包括：</p>
<ol>
<li><strong>固定位置法</strong>：逐个固定每个位置的字符</li>
<li><strong>交换策略</strong>：通过交换字符位置生成不同排列</li>
<li><strong>去重处理</strong>：使用集合(Set)或排序后跳过重复字符来避免重复排列</li>
<li><strong>字典序排序</strong>：最后对结果进行排序</li>
</ol>
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Collections;
public class StringPermutation {
public ArrayList<String> permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if (str == null || str.length() == 0) {
return result;
}
char[] chars = str.toCharArray();
permute(chars, 0, result);
Collections.sort(result); // 按字典序排序
return result;
}
private void permute(char[] chars, int begin, ArrayList<String> result) {
if (begin == chars.length - 1) {
result.add(new String(chars));
return;
}
for (int i = begin; i < chars.length; i++) {
// 跳过重复字符，避免重复排列
if (i != begin && chars == chars) {
continue;
}
swap(chars, begin, i);
permute(chars, begin + 1, result);
swap(chars, i, begin); // 回溯，恢复原始状态
}
}
private void swap(char[] chars, int i, int j) {
char temp = chars;
chars = chars;
chars = temp;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n*n!)，n为字符串长度，n!是排列总数，每次排列需要O(n)时间</li>
<li><strong>空间复杂度</strong>：O(n!)，需要存储所有排列结果</li>
</ul>
<h3 id="回溯剪枝法优化去重">回溯+剪枝法（优化去重）</h3>
<p>上面方法主要是通过Set进行去重，也可以将字符数组排序来跳过重复字符：</p>
<ol>
<li><strong>先排序</strong>：将字符数组排序，使相同字符相邻</li>
<li><strong>剪枝策略</strong>：在递归过程中跳过相同字符的重复分支</li>
<li><strong>标记数组</strong>：使用boolean数组记录已使用字符</li>
</ol>
<pre><code class="language-java">public class StringPermutation {
public ArrayList<String> permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if (str == null || str.length() == 0) {
return result;
}
char[] chars = str.toCharArray();
Arrays.sort(chars); // 先排序便于去重
boolean[] used = new boolean;
backtrack(chars, used, new StringBuilder(), result);
return result;
}
private void backtrack(char[] chars, boolean[] used,
StringBuilder path, ArrayList<String> result) {
if (path.length() == chars.length) {
result.add(path.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
// 剪枝条件：跳过已使用字符或相同字符的重复分支
if (used || (i > 0 && chars == chars && !used)) {
continue;
}
used = true;
path.append(chars);
backtrack(chars, used, path, result);
path.deleteCharAt(path.length() - 1); // 回溯
used = false;
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n*n!)，但剪枝减少了不必要的递归调用</li>
<li><strong>空间复杂度</strong>：O(n!)，结果存储空间</li>
</ul>
<h3 id="非递归">非递归</h3>
<p>此方法算法理解难度较大，非标准解法</p>
<p>用字典序生成下一个排列的算法：</p>
<ol>
<li><strong>初始排序</strong>：将字符数组按字典序排序</li>
<li><strong>找下一个排列</strong>：
<ul>
<li>从后向前找到第一个升序对</li>
<li>交换适当元素</li>
<li>反转后缀</li>
</ul>
</li>
<li><strong>循环生成</strong>：直到无法生成下一个排列</li>
</ol>
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
public class StringPermutation {
public ArrayList<String> permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if (str == null || str.length() == 0) {
return result;
}
char[] chars = str.toCharArray();
Arrays.sort(chars); // 初始排序
result.add(new String(chars));
while (true) {
int i = chars.length - 2;
// 从后向前找第一个升序对
while (i >= 0 && chars >= chars) {
i--;
}
if (i < 0) break; // 已是最大排列
int j = chars.length - 1;
// 找到第一个大于chars的字符
while (chars <= chars) {
j--;
}
swap(chars, i, j);
reverse(chars, i + 1, chars.length - 1);
result.add(new String(chars));
}
return result;
}
private void swap(char[] chars, int i, int j) {
char temp = chars;
chars = chars;
chars = temp;
}
private void reverse(char[] chars, int start, int end) {
while (start < end) {
swap(chars, start++, end--);
}
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n*n!)，每次生成下一个排列需要O(n)时间</li>
<li><strong>空间复杂度</strong>：O(n!)，结果存储空间</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19066184
頁:
[1]