Вопрос об интервью - текст Разделения в подстроки согласно правилам
Текст разделения в подстроки согласно ниже правил:
- a) Длина каждой подстроки должна меньше чем или равный M
- b) Длина подстроки должна меньше чем или равный N (N <M), если подстрока содержит какой-либо числовой символ
- c) Общее количество подстрок должно быть как можно меньше
У меня нет подсказки, как решить этот вопрос, я предполагаю, что он связан с "динамическим программированием". Кто-либо может помочь мне реализовать его с помощью C# или Java?Большое спасибо.
3 ответа
Идея
Жадный подход - лучший вариант:
- Если текущий текст пуст, все готово.
- Возьмите первые N символов. Если любой из них является цифрой, это новая подстрока. Отрубите его и переходите к началу.
- В противном случае расширить безцифровый сегмент не более чем до M символов. Это новая подстрока. Отрубите его и переходите к началу.
Доказательство
Вот доведенное до абсурда доказательство того, что приведенное выше дает оптимальное решение. Предположим, что есть лучший раскол, чем жадный. Давайте перейдем к моменту, когда два разделения начинают различаться, и удалим все, что было до этого момента.
Случай 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
Опять же, «лучшее» разбиение может быть преобразовано без изменения количества сегментов в жадное разделение, что противоречит первоначальному предположению о том, что существует лучшее разделение, чем жадное разделение.
Следовательно, жадное разделение является оптимальным. Q.E.D.
Реализация (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"));
}
}
Bolo в своем ответе привел жадный алгоритм и попросил привести контрпример. Ну, контрпримера нет, потому что это совершенно правильный подход. Вот доказательство. Хотя оно и немногословное, но часто бывает, что доказательство длиннее самого алгоритма :)
Представим, что у нас есть входные данные длины L и мы построили ответ A с помощью нашего алгоритма. Теперь предположим, что существует лучший ответ B. Т.е. у B меньше сегментов, чем у A.
Скажем, первый отрезок в A имеет длину la, а в B - lb. la >= lb, так как мы выбрали первый отрезок в A максимально возможной длины. А если lb < la, то мы можем увеличить длину первого сегмента в B без увеличения общего количества сегментов в B. Это даст нам некоторое другое оптимальное решение B', имеющее тот же первый сегмент, что и A.
Теперь удалите этот первый сегмент из A и B' и повторите операцию для длины L' < L. Делайте это до тех пор, пока не останется ни одного сегмента. Значит, ответ A равен некоторому оптимальному решению.
Результатом вычислений будет разбиение заданного текста на короткие подстроки, содержащие цифры, и длинные подстроки, не содержащие цифр. (Многое из этого вы уже знали).
По сути, вы будете разбивать короткие подстроки вокруг числительных, а затем разбивать все остальное на длинные подстроки так часто, как это необходимо для выполнения критерия длины.
Ваша свобода, т.е. то, чем вы можете манипулировать, чтобы улучшить результат, заключается в том, чтобы выбрать, какие символы включать в числовой ряд. Если N = 3, то для каждого числительного вы можете выбрать XXN, XNX или NXX. Если M равно 5, и у вас есть 6 символов перед первым цифровым символом, вы захотите включить хотя бы один из этих символов в короткую подстроку, чтобы не получить в итоге две "длинные" строки слева от "короткой", когда можно было бы ограничиться одной.
В качестве первого приближения, я бы пошел по пути расширения ваших "коротких" строк влево достаточно далеко, чтобы избежать избыточных "длинных" строк. Это типичный "жадный" подход, а жадные подходы часто дают оптимальные или почти оптимальные результаты. Сделать даже лучше, чем это, будет непросто, и я не собираюсь пытаться выяснить, как это сделать.