Menemukan semua cara yang mungkin untuk memasukkan pola ke dalam string

7

Saya sudah memikirkan masalah ini untuk sementara waktu, dan saya hanya bisa menemukan solusi rekursif tapi saya merasa ada cara pemrograman yang dinamis untuk melakukannya, saya tidak bisa mengatasinya. Apakah ini masalah terkenal yang tidak saya ketahui?

T: Diberikan string dan pola, kembalikan jumlah cara unik untuk mencocokkan huruf pola (dalam urutan) dengan string.

Klarifikasi: Untuk menemukan kecocokan, Anda mengambil karakter pertama dari pola, menemukan karakter yang cocok pertama dalam string, kemudian Anda mengambil karakter kedua dari pola dan mencocokkan dengan karakter pencocokan pertama dari string yang SETELAH Anda cocok sebelumnya dengan yang cocok karakter.

Contoh 1 (4 pertandingan):

String: DABBCDDE

Pola: ABD

Cara-cara yang mungkin (karakter yang dicetak tebal adalah tempat pola dicocokkan dengan string):

  • D AB BC D DE
  • D A B B C D DE
  • D AB BCD D E
  • D A B B CD D E

Contoh 2 (0 cocok):

String: ABC

Pola: BCA

(Anda mencocokkan B, C dan kemudian Anda berada di akhir string, Anda TIDAK dapat kembali dan mencocokkan dengan karakter sebelumnya)

Dengan pendekatan rekursif, saya memiliki metode yang melacak indeks saya di string ( sIndex ) serta pola ( pIndex ). Jika string [sIndex] cocok dengan pola [pIndex], kami memanggil metode itu lagi dan menambah sIndex dan pIndex. Jika tidak - cukup tambahkan sIndex dan coba lagi untuk menemukan kecocokan. Metode mengembalikan jumlah total karena nilai pengembalian panggilan rekursif ditambahkan bersama-sama. (Cocok tambahkan 1, tidak ada yang cocok tambahkan 0)

Kasus dasar:

  • Jika pIndex lebih besar dari panjang pola, kembalikan 0.

  • Jika sIndex lebih besar dari panjang string, kembalikan 1 (kami menemukan kecocokan!)

Apa solusi lain yang ada?

algorithms recursion dynamic-programming Daniel Olsson
sumber
Apakah nilai duplikat diperbolehkan dalam pola? Apakah kami dijamin pola dan senarnya baik-baik saja?
Brandon Arnold
Ya, nilai duplikat diizinkan dalam pola. Saya tidak tahu apakah saya membuat diri saya terlalu jelas, tetapi jika Anda mengacaukan pesanan, maka masalahnya berubah. Jadi jika Anda memiliki CBA sebagai string dan polanya adalah ABC, Anda tidak memiliki kecocokan karena kecocokan pertama adalah A, dan kemudian tidak ada lagi karakter dalam string yang cocok dengan karakter Anda yang tersisa dalam pola (BC). Apakah ini menjelaskan?
Daniel Olsson
Saya menemukan insertingcukup menyesatkan. Bukankah elemen-elemen ini cocok patterndengan elemen-elemen stringsecara berurutan?
Mai
Menghapus jawaban regex saya, karena setelah bermain di js fiddle saya menemukan itu tidak cocok dengan semua permutasi yang mungkin :(
Gavin Clarke
1
Mai, itu benar, aku akan mengubah kata-katanya.
Daniel Olsson

Jawaban:

1

Saya pikir Anda tidak perlu menggunakan Pemrograman Dinamis untuk menyelesaikan ini. Saya pikir ini solusinya:

  1. Pertama buat daftar daftar untuk mempertahankan kemunculan karakter dalam pola dalam teks yang diberikan.

  2. Akan seperti ini

Diagram berikut: 

   A    B    D 
             0 
   1 -> 2 -> 5
        3    6

  1. Ini menyiratkan (dengan asumsi 0-pengindeksan) A terjadi di posisi 0, B terjadi di posisi 2,3, D terjadi di posisi 0,5,6.

  2. Untuk masing-masing pasangan kolom berturut-turut (di sini A, B dan B, D) gunakan pointer untuk memetakan nilai yang sesuai dalam kolom ke nilai berikutnya yang lebih besar di kolom berikutnya. Di sini 1 (di col1) memiliki pointer ke 2 (di col2) dan 2 (di col2) memiliki pointer ke 5 (di col3) karena 0 lebih rendah dari 2. 3 (di col2) memiliki pointer ke 5 (di col3) ) (Saya tidak bisa menggambar di sini).

  3. Untuk setiap nilai di kolom pertama, temukan jumlah cara yang mungkin menggunakan pointer. Di sini 1 -> 2 dan 2 -> 5 dan jumlah cara yang mungkin adalah 2 * 2 cara (yaitu, 1-> 2-> 5, 1-> 2-> 6, 1-> 3-> 5, 1 -> 3-> 6). Anda hanya perlu mengalikan jumlah elemen yang tersisa di kolom untuk setiap nilai A.

  4. Di sini hanya 1 nilai untuk Column1 (yaitu, A) yang ada. Jika ada beberapa kolom, kami menghitung nilai untuk setiap nilai A menggunakan pointer dan menjumlahkan semuanya untuk mendapatkan jumlah cara.

  5. Saya pikir kompleksitasnya adalah O (n) karena untuk membangun daftar adalah O (n), ruang pointer dan waktu konstruksi adalah O (n).

kaushalpranav
sumber
Ini benar, tetapi Anda harus lebih spesifik tentang menghasilkan kemunculan huruf pola. Kompleksitas untuk itu adalah O (nm) di mana n adalah panjang pola dan m panjang teks. (kita perlu menemukan semua kejadian masing-masing lettern dalam polanya).
Adrian Buzea