Вывести все подстроки данной строки в порядке их размера - PullRequest
Новая
       35

Вывести все подстроки данной строки в порядке их размера

0 голосов
/ 22 апреля 2020

Этот код, который я использую, взят из ранее заданного вопроса. Этот вопрос задавался и отвечался много раз, но я специально прошу, чтобы порядок был указан по размеру от наибольшего к наименьшему , 

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;
}

OUTPUT: 

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: (Не в специальном порядке, кроме размера. Это просто напечатанный пример. 

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

Я мог технически просто l oop через возвращенный список и найти все самые большие подстроки, но это добавило бы слишком много шагов. Мне интересно, есть ли возможность сделать это в данном методе. Я думаю, что процесс включает в себя манипулирование итераторами i и j после каждого л oop?

1 Ответ

1 голос
/ 22 апреля 2020

Один простой способ достичь этого с минимальными изменениями - отсортировать ArrayList listOfSubstrings по длине и затем вернуть результат. Это будет просто изменение на одну строку с использованием 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).

Дополнительная операция сортировки представит O(N^2 x log(N^2)) = O(N^2 x log(N)).

Следовательно, общая сложность будет O(N^2 x log(N))

...