Cari rentetan palindrom terakhir dalam tatasusunan yang diberikan

Dalam masalah ini, kita perlu mencari rentetan palindrom terakhir dalam tatasusunan. Jika mana-mana rentetan adalah sama apabila dibaca, sama ada ia dibaca dari awal atau dari akhir, dikatakan bahawa rentetan itu adalah palindrom. Kita boleh membandingkan aksara permulaan dan akhir untuk memeriksa sama ada rentetan tertentu ialah palindrom. Satu lagi cara untuk mencari rentetan palindrom ialah membalikkan rentetan dan membandingkannya dengan rentetan asal.

Pernyataan Masalah - Kami diberi susunan panjang N yang mengandungi rentetan yang berbeza. Kita perlu mencari rentetan palindrom terakhir dalam tatasusunan yang diberikan.

Contoh Contoh

Input– arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};

Output –‘tut’

Penjelasan– Rentetan palindrom terakhir dalam tatasusunan yang diberikan ialah 'tut'.

Input– arr[] = {"werwr", "rwe", "nayan", "acd", "sdr"};

Output-"nayan"

Penjelasan – ‘nayan’ ialah rentetan palindrom terakhir dalam tatasusunan yang diberikan.

Input– arr[] = {"werwr", "rwe", "jh", "er", "rte"};

Output-""

Penjelasan – Memandangkan tatasusunan tidak mengandungi sebarang rentetan palindrom, ia mencetak rentetan kosong.

Kaedah 1

Dalam kaedah ini kita akan melelar melalui tatasusunan dari awal dan menyimpan rentetan palindrom terakhir dalam pembolehubah. Selain itu, kami membandingkan aksara permulaan dan penamat rentetan untuk memeriksa sama ada rentetan itu ialah palindrom.

Algoritma

• Tentukan pembolehubah 'lastPal' untuk menyimpan rentetan palindrom terakhir.

• Lintas tatasusunan.

• Gunakan fungsi isPalindrome() untuk menyemak sama ada rentetan pada indeks pth dalam tatasusunan ialah palindrom.

• Dalam fungsi isPalindrome(), gunakan gelung untuk melintasi rentetan.

• Membandingkan str[i] dan str[len - p - 1] aksara;

• Kembalikan benar selepas semua lelaran gelung selesai.

• Jika rentetan semasa ialah palindrom, kemas kini nilai pembolehubah 'lastPal' dengan rentetan semasa.

• Kembalikan "lastPal".

Contoh

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string &str) {
   int size = str.length();
   for (int p = 0; p < size / 2; p++) {
      // compare first ith and last ith character
      if (str[p] != str[size - p - 1]) {
          return false;
      }
   }
   return true;
}
string LastPalindrome(string arr[], int N) {
   string lastPal = "";
   for (int p = 0; p < N; p++) {
      if (isPalindrome(arr[p])) {
          // if the current string is palindrome, then update the lastPal string
          lastPal = arr[p];
      }
   }
   return lastPal;
}
int main() {
   string arr[] = {"werwr", "rwe", "nayan", "abba", "rte"};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout << "The last palindromic string in the given array is " << LastPalindrome(arr, N);
   return 0;
}

Output

The last palindromic string in the given array is abba

Kerumitan masa - O(N*K) kerana kami menggelungkan tatasusunan dan menyemak sama ada setiap rentetan ialah palindrom.

Kerumitan ruang - O(1) kerana kami menggunakan ruang malar.

Kaedah 2

Dalam kaedah ini kita akan mengulangi melalui tatasusunan bermula dari yang terakhir dan apabila kita menemui rentetan palindrom terakhir kita akan mengembalikannya. Selain itu, kami menggunakan kaedah reverse() untuk menyemak sama ada rentetan itu ialah palindrom.

Algoritma

• Lintas tatasusunan bermula dari yang terakhir.

• Gunakan fungsi isPalindrome() untuk menyemak sama ada rentetan itu ialah palindrom.

• Dalam fungsi isPalindrome(), simpan rentetan 'str' dalam pembolehubah 'temp'.

• Gunakan kaedah reverse() untuk membalikkan rentetan sementara.

• Kembalikan benar jika str dan temp adalah sama. Jika tidak, pulangkan palsu.

• Jika rentetan pada indeks ke-i ialah palindrom, kembalikan rentetan itu.

Contoh

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string &str) {
    string temp = str;
    reverse(temp.begin(), temp.end());
    return str == temp;
}

string LastPalindrome(string array[], int N) {
    for (int p = N - 1; p >= 0; p--) {
        if (isPalindrome(array[p])) {
            return array[p];
        }
    }
    // Return a default value if no palindrome is found
    return "No palindromic string found";
}

int main() {
    string arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The last palindromic string in the given array is " << LastPalindrome(arr, N);
    return 0;
}

Output

The last palindromic string in the given array is tut

Kerumitan masa - O(N*K) kerana kita melelar melalui tatasusunan dan membalikkan rentetan.

Kerumitan ruang - O(1) kerana kami tidak menggunakan ruang dinamik.

Di sini, kami mempelajari dua kaedah untuk mencari rentetan palindrom terakhir dalam tatasusunan yang diberikan. Kerumitan masa dan ruang kedua-dua kaedah hampir serupa, tetapi kod kedua lebih mudah dibaca dan lebih baik daripada yang pertama.

Selain itu, pengaturcara boleh cuba mencari rentetan terakhir dalam tatasusunan tertentu dan berlatih lebih banyak lagi.

Atas ialah kandungan terperinci Cari rentetan palindrom terakhir dalam tatasusunan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!