LeetCode LCR 014. 字符串的排列

Categories:

题目描述
思路分析
1. 解法一：回溯 + 去重剪枝（推荐）
相似题目

题目描述

✅ LCR 014. 字符串的排列

思路分析

解法一：回溯 + 去重剪枝（推荐）

核心思路：

对字符数组排序，保证相同字符相邻。

回溯时如果当前字符与前一个相同且前一个未使用，跳过以避免重复排列。

用 used 标记已选字符。

复杂度分析：

时间复杂度：O(n · n!)，其中 n 为字符串长度。

空间复杂度：O(n)，递归栈与标记数组。

class Solution {
    public String[] permutation(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        boolean[] used = new boolean[arr.length];
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();

        // 回溯生成所有排列
        dfs(arr, used, path, res);

        return res.toArray(new String[0]);
    }

    private void dfs(char[] arr, boolean[] used, StringBuilder path, List<String> res) {
        if (path.length() == arr.length) {
            res.add(path.toString());
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.append(arr[i]);
            dfs(arr, used, path, res);
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}

import "sort"

func permutation(s string) []string {
    arr := []byte(s)
    sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })
    used := make([]bool, len(arr))
    res := make([]string, 0)
    path := make([]byte, 0, len(arr))

    // 回溯生成所有排列
    var dfs func()
    dfs = func() {
        if len(path) == len(arr) {
            res = append(res, string(path))
            return
        }
        for i := 0; i < len(arr); i++ {
            if used[i] {
                continue
            }
            if i > 0 && arr[i] == arr[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, arr[i])
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    dfs()
    return res
}

相似题目

题目	难度	考察点
46. 全排列	中等	回溯
47. 全排列 II	中等	去重
51. N 皇后	困难	回溯
77. 组合	中等	回溯
567. 字符串的排列	中等	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/22919476