按大小顺序打印给定字符串的所有子字符串 [英] Print all the substrings of a given string in order by size

问题描述

此我正在使用的代码来自先前提出的问题.这个问题已经被询问并回答了很多次，但是我特别要求按大小从大到小的顺序列出订单.

This code I'm using is from this previously asked question. This question has been asked and answered plenty of times but I'm specifically asking for the order to be listed by size from largest to smallest.

public static void main(String[] args)
{
    String inputedWord = "ABIGWORD";

    for (String str : breakStringIntoPieces(inputedWord, 2))
    {
        System.out.print("\n") + str;
    }
}

                                                            //Pass in word and minimum
                                                            //substring length to print
public static List<String> breakStringIntoAllPossibleSubstrings(String str, int num)
{                                                               
    List<String> listOfSubstrings = new ArrayList<>();
    Boolean insideLoop = false;

    for(int i=0; i<=str.length()-num; i++)
    {
        for(int j=str.length(); j>=i+num; j--)
        {
            //System.out.println(str.substring(i, j));
            if (insideLoop) //This is simply to not add the complete string to the 
            {               //list. Only substrings

                listOfSubstrings.add(str.substring(i, j));
            }
            insideLoop = true;
        }
    }
    return listOfSubstrings;
}

输出:

ABIGWOR
ABIGWO
ABIGW
ABIG
ABI
AB

BIGWORD
BIGWOR
BIGWO
BIGW
BIG
BI

IGWORD
IGWOR
IGWO
IGW
IG

GWORD
GWOR
GWO
GW

WORD
WOR
WO

ORD
OR

RD

期望的输出:(除了大小以外，没有其他特殊顺序.这只是一个示例.

DESIRED OUTPUT: (In no special order other than size. This is just a typed example.

ABIGWOR
BIGWORD
ABIGWO
BIGWOR
IGWORD
GWORD
ABIGW
IGWOR
BIGWO
IGWO
ABIG
BIGW
WORD
GWOR
GWO
ORD
ABI
BIG
IGW
WOR
AB
BI
IG
GW
WO
OR
RD

从技术上讲，我可以遍历返回的列表并找到所有最大的子字符串，但这会增加太多步骤.我想知道是否可以在给定的方法中做到这一点.我认为该过程涉及在每个循环之后操纵i和j迭代器吗?

I could technically just loop through the returned list and find all the biggest substrings but that would add too many steps. I'm wondering if there's away to do it within the given method. I think the process involves manipulated the i and j iterators after each loop?

推荐答案

通过最少的更改即可实现此目的的一种简单方法是按长度对 listOfSubstrings ArrayList进行排序，然后返回结果.这只是使用 Collections.sort 进行的一行更改.

One simple way to achieve this with minimal changes would be to sort the listOfSubstrings ArrayList by length and then return the result. This will just be a one line change using Collections.sort.

public static List<String> breakStringIntoAllPossibleSubstrings(String str, int num) {                                                               
    List<String> listOfSubstrings = new ArrayList<>();

    /* Your code added here... */

    // This will sort in descending order of length
    Collections.sort(listOfSubstrings, (item1, item2) -> item2.length() - item1.length());

    return listOfSubstrings;
}

就时间复杂度而言，对于大小为 N 的字符串，生成所有子字符串的顺序为 O(N ^ 2).

In terms of time complexity, for a String of size N, generating all substrings is of the order O(N^2).

额外的排序操作将引入 O(N ^ 2 x log(N ^ 2))= O(N ^ 2 x log(N)).

An extra sorting operation will introduce O(N^2 x log(N^2)) = O(N^2 x log(N)).

因此，总体复杂度为 O(N ^ 2 x log(N))

这篇关于按大小顺序打印给定字符串的所有子字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！