Bilangan Cara Membentuk Rentetan Sasaran Diberi Kamus

1639. Bilangan Cara Membentuk Rentetan Sasaran Diberi Kamus

Kesukaran: Sukar

Topik: Tatasusunan, Rentetan, Pengaturcaraan Dinamik

Anda diberi senarai rentetan perkataan sama panjang dan sasaran rentetan.

Tugas anda adalah untuk membentuk sasaran menggunakan perkataan yang diberikan di bawah peraturan berikut:

• sasaran hendaklah dibentuk dari kiri ke kanan.
• Untuk membentuk aksara i^th (0-diindeks) sasaran, anda boleh memilih k^th watak j^th rentetan dalam perkataan jika sasaran[i] = perkataan[j][k].
• Sebaik sahaja anda menggunakan aksara k^th bagi j^th rentetan perkataan, anda tidak boleh lagi menggunakan x^th aksara mana-mana rentetan dalam perkataan di mana x <= k. Dalam erti kata lain, semua aksara di sebelah kiri atau pada indeks k menjadi tidak biasa untuk setiap rentetan.
• Ulang proses sehingga anda membentuk sasaran rentetan.

Notis bahawa anda boleh menggunakan berbilang aksara daripada rentetan yang sama dalam perkataan dengan syarat syarat di atas dipenuhi.

Kembalikan bilangan cara untuk membentuk sasaran daripada perkataan. Oleh kerana jawapannya mungkin terlalu besar, kembalikannya modulo 10⁹ 7.

Contoh 1:

• Input: perkataan = ["acca","bbbb","caca"], sasaran = "aba"
• Output: 6
• Penjelasan: Terdapat 6 cara untuk membentuk sasaran.
  • "aba" -> indeks 0 ("acca"), indeks 1 ("bbbb"), indeks 3 ("caca")
  • "aba" -> indeks 0 ("acca"), indeks 2 ("bbbb"), indeks 3 ("caca")
  • "aba" -> indeks 0 ("acca"), indeks 1 ("bbbb"), indeks 3 ("acca")
  • "aba" -> indeks 0 ("acca"), indeks 2 ("bbbb"), indeks 3 ("acca")
  • "aba" -> indeks 1 ("caca"), indeks 2 ("bbbb"), indeks 3 ("acca")
  • "aba" -> indeks 1 ("caca"), indeks 2 ("bbbb"), indeks 3 ("caca")

  Contoh 2:

  • Input: perkataan = ["abba","baab"], sasaran = "bab"
  • Output: 4
  • Penjelasan: Terdapat 4 cara untuk membentuk sasaran.
    • "bab" -> indeks 0 ("baab"), indeks 1 ("baab"), indeks 2 ("abba")
    • "bab" -> indeks 0 ("baab"), indeks 1 ("baab"), indeks 3 ("baab")
    • "bab" -> indeks 0 ("baab"), indeks 2 ("baab"), indeks 3 ("baab")
    • "bab" -> indeks 1 ("abba"), indeks 2 ("baab"), indeks 3 ("baab")

  Kekangan:

  • 1 <= perkataan.panjang <= 1000
  • 1 <= perkataan[i].panjang <= 1000
  • Semua rentetan dalam perkataan mempunyai panjang yang sama.
  • 1 <= target.length <= 1000
  • perkataan[i] dan sasaran mengandungi hanya huruf kecil Inggeris.

  Petunjuk:

  1. Untuk setiap indeks i, simpan kekerapan setiap aksara dalam baris i^th.
  2. Gunakan pengaturcaraan dinamik untuk mengira bilangan cara untuk mendapatkan rentetan sasaran menggunakan tatasusunan frekuensi.

  Penyelesaian:

  Masalahnya memerlukan mencari bilangan cara untuk membentuk rentetan sasaran daripada kamus perkataan, mengikut peraturan khusus tentang penggunaan aksara. Ini ialah masalah gabungan yang boleh diselesaikan dengan cekap menggunakan Pengaturcaraan Dinamik (DP) dan prapemprosesan frekuensi aksara.

  Perkara Penting

  1. Kekangan:
     • Perkataan adalah sama panjang.
     • Watak dalam perkataan hanya boleh digunakan dengan cara kiri ke kanan.
  2. Cabaran:
     • Mengira cara untuk membentuk sasaran dengan cekap kerana kekangan yang besar.
     • Elakkan pengiraan semula dengan menghafal.
  3. Modul:
     • Memandangkan hasilnya boleh besar, semua pengiraan dilakukan modulo 10⁹ 7.

  Pendekatan

  Penyelesaian menggunakan:

  1. Prapemprosesan:
     • Kira kekerapan setiap aksara pada setiap kedudukan merentas semua perkataan.
  2. Pengaturcaraan Dinamik:
     • Gunakan jadual DP 2D untuk mengira bilangan cara untuk membentuk rentetan sasaran.

  Langkah:

  1. Praproses perkataan menjadi tatasusunan kekerapan (kiraan).
  2. Tentukan fungsi DP untuk mencari secara rekursif bilangan cara untuk membentuk sasaran menggunakan kiraan praproses.

  Rancang

  1. Penghuraian Input:
     • Terima perkataan dan sasaran.
  2. Praproses:
     • Buat tatasusunan kiraan dengan kiraan[j][char] mewakili kekerapan aksara pada kedudukan j dalam semua perkataan.
  3. Pengaturcaraan Dinamik:
     • Gunakan fungsi rekursif dengan memoisasi untuk mengira bilangan cara membentuk sasaran menggunakan aksara daripada kedudukan yang sah dalam perkataan.
  4. Kembalikan Keputusan:
     • Kembalikan jumlah modulo 10⁹ 7.

  Mari laksanakan penyelesaian ini dalam PHP: 1639. Bilangan Cara Membentuk Rentetan Sasaran Diberi Kamus
  

  
  
  
  
  
  
    
    
    Penjelasan:
  
  
  
  
  Langkah Prapemprosesan:
  
  Bina tatasusunan kiraan:
  
  
  Untuk setiap lajur dalam perkataan, kira kejadian setiap aksara.
  
  
  Contoh: Jika perkataan = ["acca", "bbbb", "caca"], untuk lajur pertama, dikira[0] = {'a': 1, 'b': 1, 'c': 1 }.
  
  
  
  DP rekursif:
  
  
  Tentukan dp(i, j):
  
  
  
  i ialah indeks semasa dalam sasaran.
  
  j ialah kedudukan semasa dalam perkataan.
  
  
  Kes Asas:
  
  
  Jika i == len(sasaran): Keseluruhan sasaran terbentuk → pulangkan 1.
  Jika j == len(perkataan[0]): Tiada lagi lajur untuk digunakan → kembalikan 0.
  
  
  Berulang:
  
  
  Pilihan 1: Gunakan kiraan[j][sasaran[i]] aksara daripada kedudukan j.
  Pilihan 2: Langkau kedudukan j.
  
  
  
  
  
  Pengoptimuman:
  
  
  Gunakan jadual hafalan untuk menyimpan hasil submasalah yang bertindih.
  
  
  
  
  
    
    
    Contoh Panduan
  
  
  Input:
  
  
  perkataan = ["acca", "bbbb", "caca"], sasaran = "aba"
  
  
  
  Prapemprosesan:
  
  
  kiraan[0] = {'a': 2, 'b': 0, 'c': 1}
  kiraan[1] = {'a': 0, 'b': 3, 'c': 0}
  kiraan[2] = {'a': 1, 'b': 0, 'c': 2}
  kiraan[3] = {'a': 2, 'b': 0, 'c': 1}
  
  
  
  Pengiraan DP:
  
  
  
  dp(0, 0): Berapa banyak cara untuk membentuk "aba" bermula dari lajur 0.
  Kira secara rekursif, menggabungkan penggunaan kiraan dan melangkau lajur.
  
  
  
  
  Output: 6
  
  
    
    
    Kerumitan Masa
  
  
  
  
  Praproses: O(n x m), dengan n ialah bilangan perkataan dan m ialah panjangnya.
  
  Pengaturcaraan Dinamik: O(l x m), dengan l ialah panjang sasaran.
  
  Jumlah: O(n x m l x m).
  
  
  
    
    
    Output sebagai Contoh
  
  
  
  
  Input:
  perkataan = ["acca", "bbbb", "caca"], sasaran = "aba"
  
  
  Output: 6
  
  
  
  Masalah ini ialah contoh yang bagus untuk menggabungkan prapemprosesan dan pengaturcaraan dinamik untuk menyelesaikan cabaran gabungan dengan cekap.
  
  Pautan Kenalan
  
  Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
  
  Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
  
  
  LinkedIn
  GitHub
  
  
  
            
  
              
    
  
              
          

Atas ialah kandungan terperinci Bilangan Cara Membentuk Rentetan Sasaran Diberi Kamus. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!