Сортировка строки в лексикографическом порядке

Вопрос предоставляет входную строку и целое число, он просит нас преобразовать строку во все возможные комбинации подстрок длины, как указано предоставленным входным целым числом. Затем мы должны найти максимум и минимум из этих подстрок.

Я нашел решение проблемы, но может ли кто-нибудь объяснить часть цикла. Решение:

import java.io.*;`
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        String maxString = s.substring(0, k);
        String minString = s.substring(0, k);

        for (int i = 1; i <= s.length() - k; ++i){
            if (maxString.compareTo(s.substring(i, i + k)) < 0)
                maxString = s.substring(i, i + k);
            if (minString.compareTo(s.substring(i, i + k)) > 0)
                minString = s.substring(i, i + k);
        }

        System.out.println(minString);
        System.out.println(maxString);
    }
}

java string sorting lexicographic
person jishnu bhattacharyya    schedule 23.07.2018    source источник
comment
ради удобочитаемости и производительности: S.substring(i,i+k) следует выполнять только один раз, а затем сохранять   -  person Lino    schedule 23.07.2018
comment
@Lino, в этом нет необходимости, так как substring вызовет лишь небольшие накладные расходы. См.: stackoverflow .com/questions/10830004/ и заголовок stackoverflow.com/questions/20260140/   -  person Hearen    schedule 23.07.2018
comment
@Hearen, тогда хотя бы для удобочитаемости;)   -  person Lino    schedule 23.07.2018
comment
@Hearen, но зачем платить накладные расходы, какими бы небольшими они ни были, когда пользы почти нет?   -  person jingx    schedule 23.07.2018
comment
Личный стиль @jingx также полезен. конечно для себя я этого делать не буду, но тут не все так серьезно.   -  person Hearen    schedule 23.07.2018

Ответы (1)


arrow_upward
0
arrow_downward

Эти два substring станут началом

Строка maxString = S.substring(0, k); // начинаем с индекса 0

Строка minString = S.substring(0, k);

в цикле for (int i=1;i<=S.length()-k;++i) мы начинаем с index=1 до последнего возможного индекса S.length()-k, который все еще может дать нам подстроку длиной k.

Мы проходим от индекса 0 (часть инициализации) до последнего индекса S.length() - k (в цикле последняя итерация):

  1. если substring больше, мы делаем обновление maxString = S.substring(i,i+k);
  2. если меньше, чем minString, мы делаем обновление minString = S.substring(i,i+k);

Также, как упоминали Лино и jingx, я реорганизовал ваш код следующим образом:

public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int k = sc.nextInt();
    String maxString = s.substring(0, k);
    String minString = s.substring(0, k);

    for (int i = 1; i <= s.length() - k; ++i){
        String curSubstr = s.substring(i, i + k);
        System.out.println(curSubstr);
        if (maxString.compareTo(curSubstr) < 0)
            maxString = s.substring(i, i + k);
        if (minString.compareTo(curSubstr) > 0)
            minString = s.substring(i, i + k);
    }

    System.out.println(minString);
    System.out.println(maxString);
}

Проведите местный тест следующим образом:

Case #1
Input: 
HelloWorld 
2
Output:
el
ll
lo
oW
Wo
or
rl
ld
He // the min
rl // the max
person Hearen    schedule 23.07.2018
comment
Спасибо за ответ. Но можем ли мы также использовать S.length() в цикле вместо S.length()-k? - person jishnu bhattacharyya; 23.07.2018
comment
Не совсем, как я уже упоминал, это гарантирует, что the last iteration верен (не выходит за рамки) - person Hearen; 23.07.2018
comment
Выдает ошибку: Исключение в потоке main java.lang.StringIndexOutOfBoundsException: индекс строки вне диапазона: 11 в java.lang.String.substring (неизвестный источник). - person jishnu bhattacharyya; 23.07.2018
comment
Вы должны предоставить мне случай, чтобы я воспроизвел ошибку. Правильно, сам код. - person Hearen; 23.07.2018