求最長對稱子串的長度

一、簡介

確定最長對稱子字串的長度是字串操作任務中的常見挑戰。

在本教程中，我們將討論兩種有效解決此問題的 Java 方法。

2. 理解對稱子串

對稱子串是前後讀取相同的子串。例如，在字串“ abba ”中，最長的對稱子字串是“ abba ”，向前和向後讀取相同，最大長度為4。

3. 對稱子串擴展方法

該方法利用滑動視窗技術來有效地識別給定字串中的最長對稱子字串。本質上，該演算法迭代字串，從中間擴展，同時確保對稱性。

讓我們深入研究一下實現：

private int findLongestSymmetricSubstringUsingSymmetricApproach(String str) {
 int maxLength = 1;
 // Approach implementation
 }

在此方法中，我們將maxLength初始化為 1，表示回文子字串的預設長度。然後，我們將迭代輸入字串中所有可能的子字串，如下所示：

for (int i = 0; i < str.length(); i++) {
 for (int j = i; j < str.length(); j++) {
 int flag = 1;
 for (int k = 0; k < (j - i + 1) / 2; k++) {
 if (str.charAt(i + k) != str.charAt(j - k)) {
 flag = 0;
 break;
 }
 }
 if (flag != 0 && (j - i + 1) > maxLength) {
 maxLength = j - i + 1;
 }
 }
 }

在每個子字串中，我們利用嵌套循環來比較從兩端到中心的字符，檢查對稱性。此外，如果發現子字串是對稱的（ flag不是 0）並且其長度超過maxLength ，我們將使用新長度更新maxLength 。

最後，我們將返回在輸入字串中找到的對稱子字串的最大長度，如下所示：

return maxLength;

4. 使用暴力方法

蠻力方法為此問題提供了直接的解決方案。以下是我們如何實施這種方法：

private int findLongestSymmetricSubstringUsingBruteForce(String str) {
 if (str == null || str.length() == 0) {
 return 0;
 }

 int maxLength = 0;

 for (int i = 0; i < str.length(); i++) {
 for (int j = i + 1; j <= str.length(); j++) {
 String substring = str.substring(i, j);
 if (isPalindrome(substring) && substring.length() > maxLength) {
 maxLength = substring.length();
 }
 }
 }

 return maxLength;
 }

在這裡，我們詳盡地檢查輸入字串中所有可能的子字串，以識別潛在的回文子字串。此外，此過程涉及迭代字串的每個字符，將其視為子字串的潛在起點。

對於每個起始位置，此方法迭代後續字元以建構不同長度的子字串。

一旦我們建構了一個子字串，我們將它傳遞給isPalindrome()方法來判斷它是否是回文，如下所示：

private boolean isPalindrome(String str) {
 int left = 0;
 int right = str.length() - 1;
 while (left < right) {
 if (s.charAt(left) != s.charAt(right)) {
 return false;
 }
 left++;
 right--;
 }
 return true;
 }

此方法透過從兩端向中心比較字元來檢查子字串，確保字元彼此對稱鏡像。

如果子字串通過回文測試且長度超過目前的maxLength ，則將其視為最長回文子字串的候選者。在這種情況下，方法會更新maxLength變數以反映新的最大長度。

5. 結論

在本文中，我們討論瞭如何處理對稱子字串擴展方法，強調了輸入大小和計算效率等特定要求的重要性。

與往常一樣，本文的完整程式碼範例可以在 GitHub 上找到。