Идея
Жадный подход - это путь:
- Если текущий текст пуст, все готово.
- Возьмите первый Nперсонажи.Если какой-либо из них является цифрой, то это новая подстрока.Отрубите его и перейдите к началу.
- В противном случае увеличьте сегмент без цифр до максимум М символов.Это новая подстрока.Отрубите его и перейдите к началу.
Доказательство
Вот доказательство, приводящее к абсурду, что приведенное выше дает оптимальное решение.Предположим, что есть лучшее разделение, чем жадное разделение.Давайте перейдем к точке, где два разбиения начинают различаться, и удалим все до этой точки.
Случай 1) Цифра среди первых N символов.
Предположим, чтоесть вход, для которого отсечение первых N символов не может дать оптимального решения.
Greedy split: |--N--|...
A better split: |---|--...
^
+---- this segment can be shortened from the left side
Однако второй сегмент предполагаемого лучшего решения всегда можно сократить с левой стороны, а первыйрасширен до N символов без изменения количества сегментов.Следовательно, противоречие: это разделение не лучше, чем жадное разделение.
Случай 2) Нет цифры среди первых K (N
Предположим, что есть вход, для которого отсечение первых символов K не может дать оптимального решения.
Greedy split: |--K--|...
A better split: |---|--...
^
+---- this segment can be shortened from the left side
Опять же, «лучшее» разделение может быть преобразовано без изменения количества сегментов,к жадному расщеплению, что противоречит исходному предположению о том, что существует лучшее расщепление, чем жадное расщепление.
Следовательно, жадное расщепление является оптимальным.QED
Реализация (Python)
import sys
m, n, text = int(sys.argv[1]), int(sys.argv[2]), sys.argv[3]
textLen, isDigit = len(text), [c in '0123456789' for c in text]
chunks, i, j = [], 0, 0
while j < textLen:
i, j = j, min(textLen, j + n)
if not any(isDigit[i:j]):
while j < textLen and j - i < m and not isDigit[j]:
j += 1
chunks += [text[i:j]]
print chunks
Реализация (Java)
public class SO {
public List<String> go(int m, int n, String text) {
if (text == null)
return Collections.emptyList();
List<String> chunks = new ArrayList<String>();
int i = 0;
int j = 0;
while (j < text.length()) {
i = j;
j = Math.min(text.length(), j + n);
boolean ok = true;
for (int k = i; k < j; k++)
if (Character.isDigit(text.charAt(k))) {
ok = false;
break;
}
if (ok)
while (j < text.length() && j - i < m && !Character.isDigit(text.charAt(j)))
j++;
chunks.add(text.substring(i, j));
}
return chunks;
}
@Test
public void testIt() {
Assert.assertEquals(
Arrays.asList("asdas", "d332", "4asd", "fsdxf", "23"),
go(5, 4, "asdasd3324asdfsdxf23"));
}
}