字符串排列

【原题】 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串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 条评论
登录 后参与评论

相关文章

来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3749
来自专栏CodingToDie

Awesome 项目

4185
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2752
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2908
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1422
来自专栏生信技能树

基因名变化太快,比如PAM50

当然准备把这些基因跟ensembl数据库的ID对应的时候我发现少了3个,然后我搜索发现它们的symbol其实被修改了,可以说变化比较快啦,才几年时间,3 of ...

1082
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

471

扫码关注云+社区