Ini adalah pertanyaan dari Manual Perancangan Algoritma:
Misalkan Anda diberikan tiga rangkaian karakter:
X
,Y
, danZ
, di mana|X| = n
,|Y| = m
, dan|Z| = n+m.
Z
dikatakan sebagai pengocokanX
danY
jika dan hanya jikaZ
dapat dibentuk dengan menyisipkan karakter dariX
danY
dengan cara yang mempertahankan urutan karakter dari kiri ke kanan dari setiap string.Berikan algoritma pemrograman dinamis yang efisien yang menentukan apakah
Z
merupakan pengocokan dariX
danY
.Petunjuk: nilai matriks pemrograman dinamis yang Anda buat harus berupa Boolean, bukan numerik
Inilah yang saya coba:
Awalnya, saya membuat array karakter 1-D dan pointer ke karakter awal X,Y,Z masing-masing. Jika Z-pointer cocok dengan X-pointer, simpan X di array char, jika tidak, periksa hal yang sama dengan Y-pointer. Jika setiap entri dalam array char tidak berbeda dengan entri terakhirnya, Z tidak disisipkan.
Bisakah seseorang membantu saya mengatasi masalah ini?