Это вопрос из Руководства по проектированию алгоритмов:
Предположим, вам даны три строки символов:
X
,Y
иZ
, где|X| = n
,|Y| = m
и|Z| = n+m.
Z
считается перетасовкойX
иY
тогда и только тогда, когдаZ
может быть сформирован путем чередования символов изX
иY
. таким образом, чтобы поддерживать порядок символов слева направо в каждой строке.Предложите эффективный алгоритм динамического программирования, который определяет, является ли
Z
перетасовкойX
иY
.Подсказка: значения создаваемой вами матрицы динамического программирования должны быть логическими, а не числовыми.
Вот что я пробовал:
Первоначально я создал массив одномерных символов и указатели на начальные символы X, Y, Z соответственно. Если Z-указатель совпадает с X-указателем, сохраните X в массиве символов, иначе проверьте то же самое с Y-указателем. Если каждая запись в массиве символов не отличается от ее последней записи, Z не чередуется.
Может ли кто-нибудь помочь мне с этой проблемой?