字符串排列

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

相关文章

来自专栏java学习

Java每日一练(2017/8/17)

每日一句 学的到东西的事情是锻炼,学不到的是磨练。 查看以前的所有练习题目以及答案:https://mp.weixin.qq.com/mp/homepage?_...

2639
来自专栏java达人

Java初始化顺序

作者:wota 来源:http://www.cnblogs.com/miniwiki/archive/2011/03/25/1995615.html(点击文末阅...

1967
来自专栏积累沉淀

线程的分类

1.主线程 main方法。 2.精灵线程 特点: (1)设置为精灵线程的方法:setDaemon(true); (2)其他线程结束了 精灵线程也...

1758
来自专栏WindCoder

Java中的数组是对象吗?

首先说明:Java中的数组是对象,这个可以查看The Java Language Specification SE(4.3.1)可得,另外本文讨论的相关问题的结...

411
来自专栏小灰灰

JDK容器学习之LinkedHashMap (一):底层存储结构分析

LinkedHashMap 底层存储结构分析 HashMap 是无序的kv键值对容器,TreeMap 则是根据key进行排序的kv键值对容器,而LinkedH...

1765
来自专栏King_3的技术专栏

leetcode-686-Repeated String Match(重复多少次A能够找到B)

1153
来自专栏开发与安全

从零开始学C++之模板(一):函数模板、函数模板特化、重载函数模板、非模板函数重载

一、引子 考虑求两数较大值函数max(a,b) 对于a,b的不同类型,都有相同的处理形式: return a < b ? b : a; 用已有方法解决:...

1840
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十七】Set接口集合详解

三、Set接口 Set是一种不包括重复元素的Collection。它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,它同样运行nu...

3489
来自专栏用户2442861的专栏

剑指offer 33 把数组排成最小的数

转载请注明出处:http://blog.csdn.net/ns_code/article/details/28128551

792
来自专栏机器学习算法与Python学习

Python:爬虫系列笔记(6) -- 正则化表达(推荐)

在前面我们已经搞定了怎样获取页面的内容,不过还差一步,这么多杂乱的代码夹杂文字我们怎样把它提取出来整理呢?下面就开始介绍一个十分强大的工具,正则表达式! 1.了...

3508

扫码关注云+社区