黑马程序员技术交流社区

标题: 字符串消重并求所有非空子集 [打印本页]

---

作者: 曹晓涵    时间: 2012-9-16 19:58
标题: 字符串消重并求所有非空子集

1. /*
   
2. 题目：用户给一个字符串例如"abcc"，对此字符串消重，后求所有子串(例如本题的解是a/b/c/ab/ac/ba/ca/bc/cb/abc/...)
   
3. 今天做了一套学校题库中的题，以前定义一个新的字符串，用的逐个比较法判断是否存在消重，双重循环打印所有子集，非常麻烦。
   
4. 看了正则和API候发现居然有现成的方法。请问此题还有其他更好的解法么。
   
5. */
   
6. import java.util.*;
   
7. class GetSubStr
   
8. {       
   
9.         public static void main(String [] args)
   
10.         {               
    
11.                 System.out.println(getSubSequences(eliminatingDuplicate()));
    
12.         }
    
13.         //正则表达式给字符串消重复
    
14.         public static String eliminatingDuplicate()
    
15.         {
    
16.                 String str = "abcc";
    
17.                 str = str.replaceAll("(.)\\1+","$1");
    
18.                 return str;
    
19.         }
    
20.         //获取字符串的所有非空子串
    
21.         public static ArrayList<String> getSubSequences(String strings) {
    
22.                 ArrayList<String> list = new ArrayList<String>();
    
23.                 doGetSubSequences(strings, "", list);
    
24.                 //消除空字符串
    
25.                 list.remove("");
    
26.                 //对集合进行排序
    
27.                 Collections.sort(list);
    
28.                 return list;
    
29.         }
    
30.         //获取字符串的所有子集含空集和自身
    
31.         private static void doGetSubSequences(String strings, String splits,
    
32.                         ArrayList<String> list) {
    
33.                 if (strings.length() == 0) {
    
34.                         list.add(splits);
    
35.                         return;
    
36.                 }               
    
37.                 String tail = strings.substring(1);
    
38.                 doGetSubSequences(tail, splits, list);
    
39.                 doGetSubSequences(tail, splits + strings.charAt(0), list);
    
40.         }
    
41. }

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2