字符串组合

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= str.length(); i++) {
            TreeSet<String> sortedSet = new TreeSet<>();
            for (int j = 0; j + i <= str.length(); j++) {
                sortedSet.add(str.substring(j, j + i));
            }
            for (String s : sortedSet) {
                sb.append(s).append(" ");
            }
        }
        System.out.println(sb);
    }
}

在Subset的基础上进行 了一些小小的改动。

1. 子串必须是相邻字符的组合，这点其实非常简单，直接利用 contains 方法判断即可。

2. 输出组合必须去重，最初我想到的是利用Set来实现，但是其实也能通过List的contains方法来解决。

3. 子串必须按照长度顺序排列，若长度相同则按照字典顺序排列。这个写一个比较器就能够 解决了。

详细代码如下：

（PS.写得非常直白，仅做一个抛砖引玉的作用~有更好的解法欢迎分享o(^▽^)o）

关于Subset这道题目可以在LintCode/LeetCode上找到，同样的解法和解释可以参见：

https://github.com/cherryljr/LintCode/blob/master/Subsets%20II.java

欢迎大家follow我( ▼-▼ )

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        if (str.length() <= 1) {
            System.out.println(str);
        }
        List rst = new ArrayList();
        helper(rst, new StringBuilder(), 0, str);
        Collections.sort(rst, (a, b) -> a.length() == b.length()
                ? a.compareTo(b) : a.length() - b.length());
        for (int i = 0; i < rst.size(); i++) {
            System.out.print(rst.get(i) + " ");
        }
    }
    public static void helper(List rst, StringBuilder sb, int start, String str) {
        if (rst.contains(sb.toString())) {
            return;
        }
        if (sb.length() == 1) {
            rst.add(sb.toString());
        } else if (sb.length() > 1 && str.contains(sb.toString())) {
            rst.add(sb.toString());
        }
        for (int i = start; i < str.length(); i++) {
            sb.append(str.charAt(i));
            helper(rst, sb, i + 1, str);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        ArrayList<String> list = new ArrayList<>();//使用集合存储字符串
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j <= s.length(); j++) {
                String str = s.substring(i, j);
                if (!list.contains(str)) {//判断集合中是否存在重复的字符串
                             //将字符串添加到集合中
                    list.add(str);
                }
            }
        }
            //对集合中的字符串进行排序
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() == o2.length()) {
                    for (int i = 0; i < o1.length(); i++) {
                        if (o1.charAt(i) == o2.charAt(i)) {
                            continue;
                        }
                        return o1.charAt(i) - o2.charAt(i);
                    }
                }
                return o1.length()-o2.length();
            }
        });
        for (String sub : list) {
            System.out.print(sub+" ");
        }
    }
}

	

function neighbour(str) {
    var newArr = []
    for(var i = 1; i <= str.length; i++) {
        for(var j = 0; j < str.length - i + 1; j++) {
            var son = str.substring(j, j + i)
            if(newArr.indexOf(son) === -1) {
                newArr.push(son)
            }
        }
    }
    return newArr.join(' ')
}
print(neighbour(readline())) 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] in = sc.next().toCharArray(); int n = in.length;
        TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() < o2.length()) { return -1;}
                else if (o1.length() > o2.length()) {return 1;}
                else {
                    return o1.compareTo(o2);
                }
            }
        });
        for (int i=1; i<=n; i++) {
            for (int j=0; j+i<=n; j++) {
                set.add(new String(in, j, i));
            }
        }
        StringBuilder sb = new StringBuilder();
        for (String s: set) {
            sb.append(s);
            sb.append(" ");
        }
        System.out.println(sb.toString());
    }
}

python实现的思路，遍历长度为1,2，n的连续子串，遍历每个子串时将结果
加入一个临时列表temp时，遍历结束时，利用列表的sort（）方法对临时列表
temp进行排序，并加入到结果列表中。
s = input()
n = len(s)
res = []
for i in range(1, n+1):
    temp = []
    for j in range(n-i+1):
        s_t = s[j:j+i]
        if s_t not in temp :
            temp.append(s_t)
    temp.sort()
    res.extend(temp)
res = ' '.join(res)
res +=' ' 
print(res)

	importjava.util.*;



	publicclassMain{



	        publicstaticvoidmain(String args[]) {



	        Scanner sc=newScanner(System.in);



	        String str=sc.nextLine();



	        Set<String> set=newHashSet<String>();



	        char[] cstr=str.toCharArray();



	        for(inti=1;i<cstr.length+1;i++){//循环 表示共有cstr长度种 长度的字符串



	            for(intj=0;j<cstr.length-i+1;j++){//表示这个长度字符串有多少个



	                StringBuilder sb=newStringBuilder();



	                for(intk=j;k<i+j;k++){//组装字符串



	                    sb=sb.append(cstr[k]);



	                }



	                set.add(sb.toString());



	            }



	        }



	        List<String> list=newArrayList<>();



	        for(String value:set){



	            list.add(value);



	        }



	        Collections.sort(list);



	        for(inti=1;i<=cstr.length;i++) {



	            for(String vl : list) {



	                if(vl.length()==i) {



	                    System.out.print(vl + " ");



	                }



	            }



	        }



	    }



	}

#include<stdio.h>
#include<string>
#include<iostream>
#include<set>
#include<vector>
using namespace std;
int main(){
    string in;
    cin>>in;
    int i,j,n=in.length();
    vector<string> res;
    for(i=1;i<=n;i++){
        set<string> s;
        for(j=0;j<=n-i;j++)
            s.insert(in.substr(j,i).c_str());
        for(set<string>::iterator it=s.begin();it!=s.end();it++)
            res.push_back(*it);
    }
    if(res.size()==0) return 0;
    printf("%s",res[0].c_str());
    for(i=1;i<res.size();i++) printf(" %s",res[i].c_str());
    printf(" \n");
}

python三行解法

注意，这道题贼坑。题目中说“每个组合以空格分隔”，但其实在结尾还要加一个空格才可以！！

1. 首先要找到所有相邻字符串的列表。使用两层循环遍历即可。（还要去重）

2. 多key排序。根据长度和字典序排序，在python中再简单不过。

六行：

string = input()
res = set()
for i in range(1, len(string) + 1):
    for j in range(len(string) - i + 1):
        res.add(string[j:j + i])
print(" ".join(sorted(list(res), key=lambda c: (len(c), c))))

可以使用列表表达式简化成三行：

string = input()
res = {string[j:j + i] for i in range(1, len(string) + 1) for j in range(len(string) - i + 1)}
print(" ".join(sorted(list(res), key=lambda c: (len(c), c)))+" ")

#include <iostream>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
    int i, j, len;
    string s, s_tmp;
    set<string> out;
    set<string> :: iterator it;
    
    cin >> s;
    len = s.length();
    for(i = 1; i <= len; i++)
    {
        for(j = 0; j + i - 1 < len; j++)
        {
            s_tmp = s.substr(j, i);
            out.insert(s_tmp);
        }
        for(it = out.begin(); it != out.end(); it++)
        {
             cout << *it << " ";
        }
        out.clear();
    }
    cout << endl;
    
    return 0;
}

//TreeSet  既能够排序又能去重！
import java.util.Comparator;
import java.util.Scanner; import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        TreeSet<String> set = new TreeSet<>(new StringLengthComparator());
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j <= str.length(); j++) {
                set.add(str.substring(i, j));
            }
        }
        for (String i : set) {
            System.out.print(i+" ");
        }
    }
}

// 定义比较器
class StringLengthComparator implements Comparator<Object> { @Override public int compare(Object o1, Object o2) {
        String s1 = (String) o1;
        String s2 = (String) o2;
        int result = 0;
        if (s1.length() > s2.length()) {
            result = 1;
        } else if (s1.length() < s2.length()) {
            result = -1;
        } else {
            result = s1.compareTo(s2);
        }
        return result;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int cmp(const void *s1, const void *s2)
{
    char *a = (char *)s1;
    char *b = (char *)s2;
    if (strlen(a) > strlen(b)) {
        return 1;
    } else if (strlen(a) < strlen(b)) {
        return -1;
    } else {
        return strcmp(a, b);
    }
}
int main(int argc, char *argv[])
{
    char res[100][100];
    int row = 0;
    char str[100];
    scanf("%s", str);
    if (strlen(str) <= 0) {
        return 0;
    }
    for (int i = 0; i < strlen(str); ++i) {
        char tmp[100];
        int index = 0;
        tmp[index++] = str[i];
        tmp[index] = '\0';
        strcpy(res[row++], tmp);
        for (int j = i + 1; j < strlen(str); ++j) {
            tmp[index++] = str[j];
            tmp[index] = '\0';
            strcpy(res[row++], tmp);
        }
    }
    qsort(res, row, sizeof(res[0]), cmp);
    printf("%s ", res[0]);
    for (int i = 1; i < row; ++i) {
        if (strcmp(res[i], res[i - 1]) != 0) {
            printf("%s ", res[i]);
        }
    }
    printf("\n");
    return 0;
}

import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

//输入一个字符，输出该字符中相邻字符的所有组合
//解题思路：暴力加去重
public class Main {
    public static void main(String[] args) {
        HashMap<Integer,TreeSet<String>> tsMap=new HashMap();
        Scanner output = new Scanner(System.in);
        String s = output.next();
        char[] chars=s.toCharArray();
        for(int length=1;length<=s.length();length++){//i表示字符的长度
            if(length==1){
                TreeSet<String> ts= new TreeSet();
                for(int i=0;i<s.length();i++){
                    ts.add(String.valueOf(chars[i]));
                }
                tsMap.put(length,ts);
            }
            else{
                TreeSet<String> ts= new TreeSet();
                for(int index=0;index<=s.length()-length;index++){
                    ts.add(s.substring(index,index+length));
                }
                tsMap.put(length,ts);
            }
        }
        StringBuilder outputString=new StringBuilder();
        for(int key=1;key<=s.length();key++){
            TreeSet<String> ts=tsMap.get(key);
            Iterator it=ts.iterator();
            while(it.hasNext()){
                outputString.append(it.next()).append(" ");
            }
        }
        outputString.trimToSize();
        System.out.print(outputString);
    }
}