深圳网站建设资讯/建站平台有哪些

题目描述

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

思路：

怎么样循环打印几个字符的排列，可以这样想：每一个位置上每个字符都要出现一次，那么可以采用回溯法来解决，如下：

把一串字符分为以下两个部分：第一个字符， 除第一个以外的部分。

我们可以第一个字符跟其他所有的字符交换，然后固定，其他的部分又可以看作这样的一串字符。然后递归。

下面贴出Java实现的代码：

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