字符串排列

【原题】 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 【思路】 我们首先把一个字符串看成两个步骤: 1. 确定当前的字符 2. 当前字符确定,确定剩下的字符

用题中的例子来说: abc 假设当前的位置为第一个位置,则该例子中所有可能的情况为: abc(交换a,a) bac(交换a,b) cba (交换a,c) 第一个字符确定了之后,对于上面的所有情况按照同样的方法把要确定的字符和后面的字符依次交换。很显然这是一个递归的过程。 直到最后一个位置确定。

import java.util.ArrayList;

import java.util.TreeSet;
public class Solution {
//交换数组两个字符的位置
  public void swap(char[] array,int x,int y){
        char tmp=array[x];
        array[x]=array[y];
        array[y]=tmp;
    }
    public void PermutationCore(char[] chArray,TreeSet<String> list,int start){
    //
        if(start==chArray.length) //已经生成一个排列
            list.add(String.valueOf(chArray));
        for(int i=start;i<chArray.length;i++){//依次交换当前以及后面的字符,从当前位置开始
            swap(chArray,start,i);//
            PermutationCore(chArray,list,start+1);//当前字符已经确定,递归处理余下的字符
            swap(chArray,i,start);//因为当前和一个位置交换以后,还要和其它位置交换,所以要交换回来
        }
    }
     public ArrayList<String> Permutation(String str) {
         ArrayList<String> list=new ArrayList<String>();
         TreeSet<String> set=new TreeSet<>();//使用排序的set,确保有序以及唯一
         char[] chArray=str.toCharArray();
         if(str.length()==0) return list;
         PermutationCore(chArray,set,0);
         list.addAll(set);
         return list;
        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

2018 TCO Algorithm-Round 1B 600-points题解报告

Consider the set of integers between 1 and n, inclusive, and two positive intege...

763
来自专栏Python爱好者

Java基础笔记08

1165
来自专栏Ryan Miao

java继承覆盖与向上转型,权限

子类可以覆盖父类的非final成员变量和重写非final方法 private私有变量和方法只能在类的内部使用,因此子类继承的同时会被隐藏,相当于不继承 prot...

29310
来自专栏武培轩的专栏

剑指Offer-数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 思路 思路一: 利用HashSet的元素不能重复,如果有...

3176
来自专栏深度学习与计算机视觉

C++ 类的继承与派生

继承性是面向对象程序设计最重要的特性之一,使软件有了可重用性,C++提供的类的继承机制。 继承与派生的概念 一个新类从已有的类那里获得已有的特性,这种现象称为类...

1808
来自专栏青枫的专栏

java基础学习_面向对象(下)01_day08总结

============================================================================= ==...

642
来自专栏java 成神之路

常量池之字符串常量池String.intern()

3307
来自专栏Java技术

初探Java源码之ArrayList

在我们的日常开发中,集合类是我们基本上每个人都会用经常用到的东西,用着用着,突然有一天我心生好奇,那么java集合类的这些源码是什么呢?那么我打算接下来一个...

661
来自专栏Python爱好者

Java基础笔记13

1075
来自专栏编程理解

正则表达式(四):Java regex

Java 作为一种被广泛使用的编程语言,从 jdk-1.4 开始,标准库提供了 java.util.regex 包来支持正则表达式的使用。正则在 Java 中的...

1002

扫码关注云+社区