Нахождение ширины текста в зависимости от пробелов между словами (JAVA)

Question

Я работал над проблемой оптимизации, которая требует, чтобы я нашел ширину текста, который дает мне самую длинную реку.Река определяется как последовательность пробелов, которые разделены только 1 или менее символами в разных строках.Например, у меня есть следующий текст:

Вот изображение, красный «х» означает реки.

-> Река - это последовательность пробелов в разных строках, разделенных одним символом слева, справа или ни одного.Нам нужен самый длинный из них.

Текст должен быть выровнен по левому краю, но не по правому краю, и слово не может быть разделено, если оно не подходит.

Я пытался работать с длиной каждого слова, а не со всей последовательностью символов, чтобы добиться лучшего исполнения, но я не могу решить проблему таким способом.Я могу думать только о тестировании всех возможностей (минимальная ширина - длина самого длинного слова) и о том, как получить лучшее, но я не думаю, что это эффективно во времени и в пространстве.

Я не понимаюне хочу, чтобы вы решили проблему, я просто хочу знать, если вы думаете, что она может быть решена по-другому.Спасибо!

РЕДАКТИРОВАТЬ: Например, учитывая текст, я хочу вернуть ширину и длину реки.

Answer 1

Ну, я не вижу смысла говорить ДА, ВЫ МОЖЕТЕ без каких-либо подсказок, так что здесь у вас есть ...

Я полагаю, вы должны начать с определениято, что вы знаете как правила, вытекающие из базового вопроса:

Допущения:

1. Ни в одном месте строки не будет двух или более последовательных пробелов,
2. не будет переноса слов, и, следовательно, минимальная ширина будет определяться длиной самого длинного слова,
3. Пробелы в конце строки не должны рассматриваться как часть реки (яне уверен, что это будет правильным правилом, поскольку вы можете представить себе ситуации, когда у вас есть река с шестью строками, и одна линия из этих шести заканчивается раньше, потому что следующее слово слишком длинное).

Вывсе равно нужно найти длину самого длинного слова, но это только для того, чтобы установить минимальную ширину для начала.

Итак, вы знаете, что:

1. У вас естьдлинная строка, которую нужно обернуть вминимум три записи, так что третья запись должна содержать как минимум два слова (это необходимо для создания потенциального создания трехстрочной реки, что является минимумом, верно?),
2. Таким образом, вы можете рассчитать максимальную длину любой строки, то есть length of the whole string - length of the last two words - 1 (1 - пробел между двумя последними словами), деленное на 2.

.предположения и факты , вы можете просто зациклить развертывание текста в матрице (каждая ячейка содержит один символ) и исследовать, построчно, что вы находите реки, соответствующие правилам.

Answer 2

Вы не можете сделать этот алгоритм более эффективным, так как я не вижу ни одного шаблона, который вы можете использовать, чтобы "Мне не нужно пробовать эту ширину линии, она не дает мне лучший результат, чем эта ширина линии".

Таким образом, в основном вы должны попытаться найти все решения для всех линий ширины и взять лучшее.Единственная оптимизация - это когда вы начинаете с наименьшей ширины линии и начинаете с большей, и вы находите реку длиннее, чем количество строк, которые придут - тогда вам не нужно продолжать.

Например, если вы найдете самую длинную реку сЗначение 4 и ширина вашей линии достигли 4 строк, вы можете остановить ее, так как не можете найти длинную реку.