在給定陣列中查詢最後一個迴文字串

---

在這個問題中，我們需要在陣列中找到最後一個迴文字串。如果任何字串在讀取時是相同的，無論是從開頭開始讀取還是從結尾開始讀取，我們都可以說該字串是迴文。我們可以比較開頭和結尾的字元來檢查特定的字串是否為迴文。另一種查找回文字串的方法是反轉字串並將其與原始字串進行比較。

問題陳述 – 我們給定了一個長度為 N 的陣列，其中包含不同的字串。我們需要在給定的陣列中找到最後一個迴文字串。

示例

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

輸出 – ‘tut’

解釋 – ‘tut’ 是給定陣列中的最後一個迴文字串。

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

輸出 – ‘nayan’

解釋 – ‘nayan’ 是給定陣列中的最後一個迴文字串。

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

輸出 – “”

解釋 – 由於陣列不包含任何迴文字串，因此它列印空字串。

方法 1

在這種方法中，我們將從開頭開始遍歷陣列，並將最後一個迴文字串儲存在一個變數中。此外，我們將比較字串的開頭和結尾的字元以檢查字串是否為迴文。

演算法

• 定義變數 ‘lastPal’ 來儲存最後一個迴文字串。

• 遍歷陣列。

• 使用 isPalindrome() 函式檢查陣列中第 p 個索引處的字串是否為迴文。

• 在 isPalindrome() 函式中，使用迴圈遍歷字串。

• 比較 str[i] 和 str[len - p - 1] 字元；如果任何字元不匹配，則返回 false。

• 迴圈完成後返回 true。

• 如果當前字串是迴文，則使用當前字串更新 ‘lastPal’ 變數的值。

• 返回 ‘lastPal’。

示例

#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;
}

輸出

The last palindromic string in the given array is abba

時間複雜度 – O(N*K)，因為我們遍歷陣列並檢查每個字串是否為迴文。

空間複雜度 – O(1)，因為我們使用常數空間。

方法 2

在這種方法中，我們將從最後開始遍歷陣列，當我們從最後找到第一個迴文字串時，我們將返回它。此外，我們使用 reverse() 方法來檢查字串是否為迴文。

演算法

• 從最後遍歷陣列。

• 使用 isPalindrome() 函式檢查字串是否為迴文。

• 在 isPalindrome() 函式中，將 ‘str’ 字串儲存在 ‘temp’ 變數中。

• 使用 reverse() 方法反轉 temp 字串。

• 如果 str 和 temp 相等則返回 true。否則，返回 false。

• 如果第 i 個索引處的字串是迴文，則返回該字串。

示例

#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;
}

輸出

The last palindromic string in the given array is tut

時間複雜度 – O(N*K)，因為我們遍歷陣列並反轉字串。

空間複雜度 – O(1)，因為我們沒有使用動態空間。

在這裡，我們學習了兩種在給定陣列中查詢最後一個迴文字串的方法。兩種方法的時間和空間複雜度幾乎相同，但第二段程式碼更易讀，並且比第一段程式碼更好。

此外，程式設計師可以嘗試在給定陣列中找到倒數第二個字串，並進行更多練習。