字符串的排列_

推荐

Java

偏北

 /**
     * 1、递归算法
     *
     * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     *
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation(String str){

        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        return list;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            for(int j=i;j<chars.length;++j){
                if(j==i || !charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }

    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }

/**
     * 2、字典序排列算法
     *
     * 可参考解析： http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html  （感谢作者）
     *
     * 一个全排列可看做一个字符串，字符串可有前缀、后缀。
     * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
     * 这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
     *
     * [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321，
     * 从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。
     *
     * 【例】 如何得到346987521的下一个
     * 1，从尾部往前找第一个P(i-1) < P(i)的位置
     * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
     * 最终找到6是第一个变小的数字，记录下6的位置i-1
     *
     * 2，从i位置往后找到最后一个大于6的数
     * 3 4 6 -> 9 -> 8 -> 7 5 2 1
     * 最终找到7的位置，记录位置为m
     *
     * 3，交换位置i-1和m的值
     * 3 4 7 9 8 6 5 2 1
     * 4，倒序i位置后的所有数据
     * 3 4 7 1 2 5 6 8 9
     * 则347125689为346987521的下一个排列
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation2(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str==null || str.length()==0){
            return list;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true){
            int lIndex = len-1;
            int rIndex;
            while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                lIndex--;
            }
            if(lIndex == 0)
                break;
            rIndex = lIndex;
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                rIndex++;
            }
            swap(chars,lIndex-1,rIndex-1);
            reverse(chars,lIndex);

            list.add(String.valueOf(chars));
        }

        return list;
    }

    private void reverse(char[] chars,int k){
        if(chars==null || chars.length<=k)
            return;
        int len = chars.length;
        for(int i=0;i<(len-k)/2;i++){
            int m = k+i;
            int n = len-1-i;
            if(m<=n){
                swap(chars,m,n);
            }
        }

    }

编辑于 2018-12-26 14:11:30 回复(38)

Java

牛客499848474号

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> result = new ArrayList<String>();
        if (str == null) {
            return result;
        }
        Set<String> set = new HashSet<String>();
        char[] array = str.toCharArray();
        helper(array, 0, set);
        //用hashset是为了去重，如果是arraylist的话会有重复
        for(String s : set){
            result.add(s);
        }
        return result;
    }

    private void helper(char[] array, int index, Set<String> set) {
        if (index == array.length) {
            set.add(new String(array));
            return;
        }

        for (int i = index; i < array.length; i++) {
            swap(array, index, i);
            helper(array, index + 1,set);
            swap(array, index, i);
        }
    }

    private void swap(char[] array, int i, int j) {
        char k = array[i];
        array[i] = array[j];
        array[j] = k;
    }
}

发表于 2024-09-17 17:40:18 回复(0)

Java

牛客348570162号

public ArrayList<String> Permutation (String str) {
        HashSet<String> set = new HashSet<>();
        p(str.toCharArray(),0,set);
        return new ArrayList<String>(set);
    }

    public void p(char[] str,int start,HashSet<String> set){
        if(start == str.length) set.add(new String(str));
        for(int i=start;i<str.length;i++){
            if(i>start && str[start] == str[i]) continue;
            swap(str,start,i);
            p(str,start+1,set);
            swap(str,start,i);
        }
    }

    public void swap(char[] str,int i,int j){
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

发表于 2024-09-10 11:26:23 回复(0)

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        char[] chs = str.toCharArray();
        backTrack(chs);
        return res;
    }

    ArrayList<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    HashSet<Integer> used = new HashSet<>(); // 记录每个path（纵向）使用过的字符索引 
    private void backTrack(char[] chs) {
        if (path.length() == chs.length) {
            res.add(path.toString());
            return;
        }

        HashSet<Character> usedRow = new HashSet<>();  // 记录每层使用过的字符
        for (int i = 0; i < chs.length; i++) {
            if (used.contains(i) || usedRow.contains(chs[i])) continue;
            path.append(chs[i]);
            used.add(i);
            usedRow.add(chs[i]);
            backTrack(chs);
            path.delete(path.length() - 1, path.length());
            used.remove(i);
        }
    }
}

发表于 2024-08-03 20:54:28 回复(1)

Java

人间水长东

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        // 左程云老师讲过全排列的分支限界递归法解决不重复全排列问题
        // 调用一个递归函数，这个递归函数负责对当前i位置的字符进行与i ~ chars.length - 1中的位置依次互换，然后继续考察i + 1处的情况
        // 分支界限法去重：定义一个HashSet，这个位置没有出现过该值才允许进入分支，否则跳过

        // 算法的时间复杂度0(N!)，额外空间复杂度0(N!)

        // 用于记录所有路径的结果
        ArrayList<String> finalResults = new ArrayList<>();

        // 调用这个递归函数，从num数组的0位置开始，将每一次找到的oneResult填进finalResult中
        process(str.toCharArray(), finalResults, 0);

        // 返回最终的答案finalResults
        return finalResults;
    }

    public void process(char[] chars, ArrayList<String> finalResults, int i) {
        // 递归出口（底部）
        if (i == chars.length) {
            // i越界了，说明整个数组遍历完毕了，将单个路径上的答案oneResult写入总答案finalResults中
            finalResults.add(String.valueOf(chars));
        }

        // 递归分支
        HashSet<Character> set = new HashSet<>();
        for (int j = i; j < chars.length; j++) {
            if (!set.contains(chars[j])) {
                // 将num[j]登记
                set.add(chars[j]);
                // 假设本位置与j位置的元素交换
                swap(chars, i, j);
                // 在交换完的基础上继续考察num数组中i+1往后的位置该如何排列
                process(chars, finalResults, i + 1);
                // 注意！恢复现场，继续尝试将本位值与num[j + 1]位置的元素交换
                // 踩坑点2：一定要【恢复现场】，要不然无法准确列出要分支的情况
                swap(chars, j, i);
            }
        }
    }

    // 数组元素交换函数
    public void swap(char[] chars, int i, int j) {
        if (i == j) {
            return;
        }
        char t = chars[i];
        chars[i] = chars[j];
        chars[j] = t;
    }
}

发表于 2024-07-28 22:26:34 回复(0)

Java

牛客839384289号

HashSet<String> res=new HashSet<>();

public ArrayList<String> Permutation (String str) {
    // write code here
    dfs(str.toCharArray() ,new boolean[str.length()] ,new StringBuilder());
    return new ArrayList<String>(res);
}

public void dfs(char[] cs ,boolean[] flag ,StringBuilder sb){
    if(sb.length()==cs.length){
        res.add(sb.toString());
        return;
    }
    for(int i=0;i<cs.length;i++){
        if(flag[i]){
            continue;
        }
        flag[i]=true;
        sb.append(cs[i]);
        dfs(cs ,flag ,sb);
        sb.deleteCharAt(sb.length()-1);
        flag[i]=false;
    }
}

发表于 2024-03-02 15:02:26 回复(0)

Java

-Panda君-

/*
全排列版本
*/
public class Solution {
    public ArrayList<String> Permutation (String str) {
        // write code here
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        str = new String(charArray);
        ArrayList<String> res = new ArrayList<>();
        String list = "";
        boolean[] visit = new boolean[str.length()];
        dfs(str,res,list,visit);
        return res;

    }
    private void dfs(String str,ArrayList<String> res,String list,boolean[] visit){
        if(str.length() == list.length()){
            res.add(list);
            return;
        }

        for(int i =0;i<str.length();i++){
            if(visit[i] || i>0&&str.charAt(i)==str.charAt(i-1) && visit[i-1]){
                continue;
            }
            visit[i] = true;
            list += str.charAt(i);
            dfs(str,res,list,visit);
            list = list.replaceAll(".$","");
            visit[i] = false;
        }
    }
}

发表于 2024-01-30 10:55:41 回复(0)

Java

没有字的回音

递归

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        if (str.length() < 2) {
            return new ArrayList<String>(Arrays.asList(str));
        }

        ArrayList<String> possibles = new ArrayList<String>();

        for (int i = 0; i < str.length(); i++) {
            String prefix = String.valueOf(str.charAt(i));
            String leftPart = str.substring(0, i);

            // Skip duplicates
            if (leftPart.contains(prefix)) {
                continue;
            }

            ArrayList<String> results = Permutation(
                // String without current character
                leftPart + str.substring(i + 1, str.length())
            );
            
            results.forEach((result) -> {
                possibles.add(prefix + result);
            });
        }

        return possibles;
    }
}

发表于 2023-10-05 20:16:50 回复(0)

Java

做则必成的勇气和信心

public ArrayList<String> Permutation (String str) {
        // 全排列
        //String变char[]
        char[] charrr=str.toCharArray();//String变char[]:str.toCharArray()
        //排序（去重必然排序
        Arrays.sort(charrr);
        boolean[] used=new boolean[str.length()];
        ArrayList<String> ans=new ArrayList<>();
        ArrayList<Character> list=new ArrayList<>();//作为path
        build(charrr,used,ans,list);
        return ans;
    }
    public void build(char[] charrr,boolean[] used,ArrayList<String> ans,ArrayList<Character> list){
        //截至条件:list.size()==char.length
        //把char拼接到String上 用StringBuilder
        if(list.size()==charrr.length){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<list.size();i++){
                sb.append(list.get(i));
            }
            ans.add(sb.toString());  //把StringBuilder变成String,  sb.toString()
            return;
        }
        for(int i=0;i<charrr.length;i++){
            //剪枝
            //被用过是true
            if(used[i]==true) continue;
            if(i>0&&charrr[i]==charrr[i-1]&&used[i-1]==true) continue;
            list.add(charrr[i]);
            used[i]=true;
            build(charrr,used,ans,list);
            list.remove(list.size()-1);
            used[i]=false;
        }

    }

发表于 2023-07-15 13:45:28 回复(0)

Java

精灵鼠201906031611131

交换的思路，为啥会超时呢？之前通过的代码，现在超时了

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> list = new ArrayList<String>();
       if(str!=null&&str.length()>0) {
          helper(str.toCharArray(), 0, list);
          Collections.sort(list);
       }
        return list;
    }
    
    public void helper(char[] chars, int i, ArrayList<String> list) {
        int len = chars.length;
        if(i==len-1) {
            String s = String.valueOf(chars);
            if(!list.contains(s)){
                list.add(s);
            }
        } else{
            for(int j=i; j<len; j++) {
                swap(chars, i, j);
                helper(chars, i+1, list);
                swap(chars, i, j);
            }
        }
    }
    
    public void swap(char[] cs, int i, int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}

发表于 2023-06-05 16:03:29 回复(0)

Java

Zhima1234

public class Solution {
    public ArrayList<String> Permutation(String str) {
        // 将字符串转为字符数组
        char[] sArray = str.toCharArray();
        // 排序，为了后面对树层去重
        Arrays.sort(sArray);
        // 路径
        LinkedList<Character> track = new LinkedList<>();
        // 结果集
        ArrayList<String> ans = new ArrayList<>();
        // 辅助树枝去重和树层去重
        boolean[] used = new boolean[sArray.length];
        backTrack(sArray, track, ans, used);
        return ans;
    }
    private void backTrack(char[] sArray, LinkedList<Character> track,
                           ArrayList<String> ans, boolean[] used) {
        //收获结果
        if (sArray.length == track.size()) {
            ans.add(parseToString(track));
            return;
        }
        for (int i = 0; i < sArray.length; i++) {
            // 同一个树枝上一个数不可以出现两次
            if (used[i]) {
                continue;
            }
            // 同一层不能选择同一个数
            if (i > 0 && sArray[i] == sArray[i - 1] && !used[i - 1]) {
                continue;
            }
            // 标记本次选择
            used[i] = true;
            // 做出选择
            track.addLast(sArray[i]);
            backTrack(sArray, track, ans, used);
            // 撤销标记本次选择
            used[i] = false;
            // 撤销选择
            track.removeLast();
        }
    }
    private String parseToString(LinkedList<Character> track) {
        // 将track转变为字符串返回
        StringBuilder ans = new StringBuilder();
        for (Character c : track) {
            ans.append(c);
        }
        return ans.toString();
    }
}

发表于 2023-05-30 21:11:59 回复(0)

Java

BlueProtocol

本来想用全排列来做的，没想到超时了，但是通过率91.67%

import java.util.ArrayList;

import java.util.stream.Collectors;
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        char[] chars = str.toCharArray();
        ArrayList<String> list = new ArrayList<String>();
        if (str == null || str == "") {
            list.add("");
            return list;
        }
        per(chars, new Stack(), list, chars.length);
        return list;

    }
    public void per(char[] arr, Stack stack, List<String> list, int size) {
        if (arr.length <= 0) {
            Character[] character = new Character[size];
            stack.copyInto(character);
            String str = Arrays.stream(character).map(String::valueOf).collect(
                             Collectors.joining());
            if (!list.contains(str)) {
                list.add(str);
            }
        } else {
            for (int i = 0; i < arr.length; i++) {
                char[] tempChars = new char[arr.length - 1];
                System.arraycopy(arr, 0, tempChars, 0, i);
                System.arraycopy(arr, i + 1, tempChars, i, arr.length - 1 - i);
                stack.push(arr[i]);
                per(tempChars, stack, list, size);
                stack.pop();
            }
        }
    }
}

发表于 2023-03-21 09:36:22 回复(0)

Java

Hadoopdoop

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        if (Objects.isNull(str) || str.isEmpty()) return new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        generatStr(str, 0, set);
        return new ArrayList(set);
    }

    private void generatStr(String str, int i, HashSet<String> set) {
        char[] chars = str.toCharArray();
        // 第i位置的字符与str后面每个位置换一遍
        for (int i1 = i; i1 < chars.length; i1++) {
            char temp = chars[i];
            chars[i] = chars[i1];
            chars[i1] = temp;
            set.add(String.valueOf(chars));
            // 得到的新字符串，再接着与后面的交换(如题目画的图那样)
            generatStr(String.valueOf(chars), i + 1, set);
        }
    }
}

发表于 2023-03-09 21:48:07 回复(0)

Java

键盘都敲坏了.

import java.util.*;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        char[] chars = str.toCharArray();
        Permutation(chars, res, 0);

        return res;
    }
    public void Permutation(char[] chars, ArrayList<String> res, int i) {
        if(i == chars.length){
            res.add(new String(chars));
            return;
        }
        // 每一层都使用一个hashset 来保存没有重复的字符，如果有重复，则不递归尝试获取排列
        HashSet<Character> temp = new HashSet<>();
        // 每个j位置的数都有机会来到i位置
        for (int j = i; j < chars.length; j++) {
            // 只要set中不包含j索引的字符，那么递归求解
            if(!temp.contains(chars[j])){
                // 添加记录
                temp.add(chars[j]);
                // 交换位置
                permutationSwap(chars, i, j);
                // 递归求解
                Permutation(chars, res, i+1);
                // 交换回来，下次循环继续
                permutationSwap(chars, i, j);
            }
        }
    }
    public void permutationSwap(char[] chars, int i, int j){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

发表于 2022-11-20 13:02:05 回复(0)

Java

胆小的小师弟还是想躺平

import java.util.ArrayList;

import java.util.*;

public class Solution {

ArrayList<String> list = new ArrayList<>();

Map<String,Integer> map = new HashMap<>();

public ArrayList<String> Permutation(String str) {

if(str.length()==0)return list;

char[] chars = str.toCharArray();

boolean[] vis = new boolean[chars.length];

swap(chars,"",vis);

return list;

}

public void swap(char[] chars,String cur,boolean[] vis){

if(chars.length==cur.length() && !map.containsKey(cur)){

map.put(cur,1);

list.add(cur);

return;

}

for(int i = 0;i<chars.length;i++){

if(!vis[i]){

cur+=chars[i];

vis[i]=true;

swap(chars,cur,vis);

cur=cur.substring(0,cur.length()-1);

vis[i]=false;

}

发表于 2022-11-08 16:12:21 回复(0)

Java

INEEDSSD

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> result = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        char[] charArr = str.toCharArray();
        Arrays.sort(charArr);
        backTrack(result, sb, charArr, new boolean[charArr.length]);
        return result;
    }
    
    private void backTrack(ArrayList<String> result, StringBuilder sb, char[] charArr, boolean[] visited) {
        if (sb.length() == charArr.length) {
            result.add(sb.toString());
            return;
        }
        for (int i = 0; i < charArr.length; i++) {
            if (visited[i]) continue;
            if (i > 0 && charArr[i - 1] == charArr[i] && visited[i - 1]) continue;
            visited[i] = true;
            sb.append(charArr[i]);
            backTrack(result, sb, charArr, visited);
            visited[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }       
    }
}

发表于 2022-09-16 09:25:21 回复(0)

Java

那咋办嘛66

import java.util.ArrayList;
public class Solution
{//1

public ArrayList<String> PermutationHelp(StringBuilder str){//2
ArrayList<String> result = new ArrayList<String>();
if(str.length() == 1)result.add(str.toString());
else{//3
for(int i = 0; i < str.length(); i++){//4
if(i== 0 || str.charAt(i) != str.charAt(0)){//5
char temp = str.charAt(i);
str.setCharAt(i, str.charAt(0));
str.setCharAt(0, temp);
ArrayList<String> newResult = PermutationHelp(new StringBuilder(str.substring(1)));
for(int j =0; j < newResult.size(); j++)
result.add(str.substring(0,1)+newResult.get(j));
//用完还是要放回去的
temp = str.charAt(0);
str.setCharAt(0, str.charAt(i));
str.setCharAt(i, temp);
}//5
}//4
//需要在做一个排序操作

}//3
return result;
}//2

public ArrayList<String> Permutation(String str) {
StringBuilder strBuilder = new StringBuilder(str);
ArrayList<String> result = PermutationHelp(strBuilder);
return result;
}
}//1

发表于 2022-09-14 19:51:28 回复(0)

Java

dfs暴力粗奇迹

java的swap也会超时试了几个版本答案最后一个case都会超时

发表于 2022-08-29 15:36:44 回复(0)

字符串的排列

输入描述:

输入

输出

说明

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题