[名企面试知识点][Java]字符串的顺序全排列
发布于 2017-03-08 13:28 1353 次浏览 0 赞 来自 笔试面试  

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。

输入描述

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

输出描述

顺序输出字符串的所有排列

题目分析

这是一个字符串全排列的问题,把全部序列存在TreeSet中默认可得到字典顺序。

TreeSet     基于TreeMap实现的SortedSet,可以对Set集合中的元素进行排序,排序后按升序排列元素(缺省是按照自然排序),非线程安全。

思路:

固定一个字符串之后,之后再将问题变小,只需求出后面子串的排列个数就可以得出结果,然后依次将后面的字符串与前面的交换,再递归子串的排列结果,最后当所有字符都固定结束递归。

下面这张图很清楚的给出了递归的过程:

解法 运行时间:131ms 占用内存:1477k 

import java.util.*;
public class Solution {
   //用于最后返回结果
   ArrayList<String> list  = new ArrayList<>();
   //遍历的时候来存储序列实现排序
   TreeSet<String> set = new TreeSet<>();

   public ArrayList<String> Permutation(String str) {      
      if(str==null || str.length()==0) return list;

      Permutation(str.toCharArray(),0);
      //容器转换
      list.addAll(set);
      return list;
   }
   public void Permutation(char[] s,int index){
       if(s==null ||s.length==0 || index<0 || index>s.length-1)  return ;
       if(index==s.length-1){//递归固定到最后一个位置,把该串加入集合
           set.add(new String(s));
       }else{//固定前index+1个字符,递归后面所有可能的子串
          for(int i = index;i<s.length;i++){
              swap(s,index,i);//交换一次形成一个子串
              Permutation(s,index+1);
              swap(s,i,index);//复原使下次循环产生下一个子串
          }
       }
   }
   public void swap(char[] s,int i,int j){
       char temp = s[i];
       s[i] = s[j];
       s[j] = temp;
   }
}


添加回复
回到顶部