本帖最后由 ddewym123 于 2014-8-11 21:50 编辑
我今天做了下这道题。确实好麻烦。
我一开始只想到了递归方法(水平有限,实在没办法)。在参考了7楼zeus00456兄的思路后,写了非递归方法。
下面是我的代码,仅供参考:- import java.util.ArrayList;
- import java.util.HashSet;
- import java.util.List;
- import java.util.Set;
- import java.util.regex.Matcher;
- import java.util.regex.Pattern;
- public class StringDemo {
- public static void main(String[] args) {
- String str="abcd";
- //方法一:递归方法
- List<String> subStrs=getSubStr(str);//获取所有的子串
- List<String> stringSet=new ArrayList<String>();//用于添加所有的排列组合
- //获取每个子串的排列情况并添加进stringSet
- for(String string:subStrs){
- List<String> oldSet=arrangeStr(string,string.length());
- for(String arrangedStr:oldSet){
- stringSet.add(arrangedStr);
- }
- }
- System.out.println(stringSet);
-
- //方法二:非递归方法
- /*char[] chs=str.toCharArray();
- List<String> stringSet=new ArrayList<String>();
- int len=str.length();
- //获取所有的排列组合
- for (int i = 1; i <= len; i++) {
- Set<String> oldSet=getArrangedStr(chs,i);
- for(String string:oldSet){
- stringSet.add(string);
- }
- }
- System.out.println(stringSet);*/
- }
- //方法一:递归方法
- //找出该字符串的所有子串
- private static List<String> getSubStr(String str) {
- List<String> newSet=new ArrayList<String>();
- for (int i = 1; i <= str.length(); i++) {
- List<String> oldSet=subStr(str,i);
- for (String string:oldSet) {
- newSet.add(string);
- }
- }
- return newSet;
- }
- //获取num长度的子串
- private static List<String> subStr(String str,int num){
- List<String> newSet=new ArrayList<String>();
- //如果要求子串长度为1,则每个字母都是子串
- if(num==1){
- for(int i=0;i<str.length();i++){
- newSet.add(str.charAt(i)+"");
- }
- return newSet;
- }
- //如果要求子串长度为n,在确定首字母的情况下,递归获取剩下n-1位子串,然后拼凑起来
- for(int i=0;i<str.length()-1;i++){
- char c=str.charAt(i);
- List<String> oldSet=subStr(str.substring(i+1),num-1);
- for(String string:oldSet){
- newSet.add(c+string);
- }
- }
- return newSet;
- }
- //排列字符串
- private static List<String> arrangeStr(String str,int len) {
- List<String> newSet=new ArrayList<String>();
- //如果字符串长度为1,则该字符串就只有一种排列情况
- if(len==1){
- newSet.add(str);
- return newSet;
- }
- //如果字符串长度为n,在确定首字母的情况下,递归获取剩下n-1长度的字符串的排列情况,然后拼凑起来
- for (int i = 0; i < len; i++) {
- StringBuilder sb=new StringBuilder(str);
- char c=sb.charAt(i);
- List<String> oldSet=arrangeStr(sb.deleteCharAt(i).toString(),len-1);
- for (String string:oldSet) {
- newSet.add(c+string);
- }
- }
- return newSet;
- }
- //方法二:非递归方法
- //获取长度为i的子串的所有排列情况
- private static Set<String> getArrangedStr(char[] chs, int i) {
- Set<String> hs=new HashSet<String>();
- /*对于每一种长度i,将它当成一个i位的,
- 每一位有chs.length种情况的chs.length进制数,
- 从这个0开始遍历到最大值,每一个数都是一种排列情况*/
- for (int j = 0; j < Math.pow(chs.length, i); j++) {
- StringBuilder sb=new StringBuilder();
- String string=Integer.toString(j, chs.length);//转换成chs.length进制值
- string=String.format("%0"+i+"d", Integer.parseInt(string));//前面补0,保证字符串都是i位的
- //产生一种排列情况,即一个子串
- for (int k = 0; k < string.length(); k++) {
- sb.insert(0,chs[Integer.parseInt(""+string.charAt(k))]);
- }
- String newStr=sb.toString();
- //去除包含重复字母的子串
- if(checkStr(newStr))
- hs.add(sb.toString());
- else
- continue;
- }
- return hs;
- }
- //判断子串是否包含重复字母
- private static boolean checkStr(String newStr) {
- String regex="(\\w)\\w*\\1+";
- Pattern pattern=Pattern.compile(regex);
- Matcher matcher=pattern.matcher(newStr);
- return !matcher.find();
- }
- }
复制代码
|