欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 剑指offer Q38字符串的排列

程序员文章站 2024-01-22 11:06:40
...

思路

求一个字符串的全排列组合,直接想到使用回溯中的全排列算法。
回顾一下全排列算法:
假设 需要排列 abc。
下图表示了整个递归过程。对abc进行全排列就是有三个位置用abc去填,全排列算法使用交换来实现填入操作。如图,第一层递归拿到abc,固定住第一个元素,然后使用循环的方式分别将后面的每个元素和第一个元素进行交换,这样一次层递归便将第一个位置的字母确定了,然后进入在循环中进入下一层递归去确定下一个位置的元素,这样直到到达最后一个元素时,将此次序列输出,顺便进行去重操作。
LeetCode 剑指offer Q38字符串的排列

代码

package algorithm.jianzhiOffer;

import java.util.*;

public class Q38 {
    List<String> res;
    Set<String> a;
    int len;

    public String[] permutation(String s) {
        len = s.length();
        a = new HashSet<>();
        res = new ArrayList<>();
        String[] ss = s.split("");
        sub(ss, 0);

        return res.toArray(ss);
    }

    void sub(String[] s, int k) {
        if (k == len-1) {
            StringBuffer re = new StringBuffer();
            for (String ch : s)
                re.append(ch);
            if (!a.contains(re.toString())) {
                res.add(re.toString());
                a.add(re.toString());
            }
        } else {
            for (int i = k; i < len; i++) {
                swap(s, k, i);
                sub(s, k+1);
                swap(s, k, i);
            }
        }
    }

    void swap(String[] s, int i, int j) {
        String temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    public static void main(String[] argc) {
        String[] qq=new Q38().permutation("adbc");
        return;
    }

}

相关标签: LeetCode每日一题

上一篇: leetcode 401: 二进制手表

下一篇: