在給定的陣列中找到最後一個回文字串

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

問題陳述 - 我們給定一個長度為N的數組，其中包含不同的字串。我們需要找到給定數組中的最後一個回文字串。

範例範例

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

輸出 – ‘tut’

Explanation– 給定陣列中的最後一個回文字串是‘tut’。

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

輸出-“nayan”

Explanation – ‘nayan’是給定陣列中的最後一個回文字串。

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

輸出-“”

說明 – 由於陣列不包含任何回文字串，因此它會列印空字串。

方法 1

在這種方法中，我們將從頭開始遍歷數組並將最後一個回文字串儲存在變數中。另外，我們也會比較字串的開頭和結尾字符，以檢查字串是否是回文。

演算法

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

• 遍歷陣列。

• 使用isPalindrome()函數來檢查陣列中第pth索引處的字串是否為回文。

• 在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()方法反轉暫存字串。

• 如果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)，因為我們不使用動態空間。

在這裡，我們學習了兩種方法來找到給定數組中的最後一個回文字串。這兩種方法的時間和空間複雜度幾乎相似，但第二個程式碼比第一個更容易閱讀且更好。

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

以上是在給定的陣列中找到最後一個回文字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！