回文子串和回文鏈表

文章目錄

• • 回文子串和回文鏈表
  • 一、最長回文子串
  • • 1.題目描述
    • 2.分析
    • 3.代碼實現
  • 二、判斷回文鏈表
  • • 1.問題描述
    • 2. 分析
    • 3.代碼
    • 4.優化
  • 三、回文子串
  • • 1.問題描述
    • 2.代碼

一、最長回文子串

1.題目描述

2.分析

• 對于這個問題，我們首先應該思考的是，給一個字符串 s，如何在 s 中找到一個回文子串？
• 有一個很有趣的思路：既然回文串是一個正著反著讀都一樣的字符串，那么如果我們把 s 反轉，稱為 s’，然后在 s 和 s’ 中尋找最長公共子串，這樣應該就能找到最長回文子串。
• 比如說字符串 abacd，反過來是 dcaba，它的最長公共子串是 aba，也就是最長回文子串。
• 但是這個思路是錯誤的，比如說字符串 aacxycaa，反轉之后是 aacyxcaa，最長公共子串是 aac，但是最長回文子串應該是 aa。
• 雖然這個思路不正確，但是這種把問題轉化為其他形式的思考方式是非常值得提倡的。
• 下面，就來說一下正確的思路，如何使用 雙指針。
• 尋找回文串的問題核心思想是：從中間開始向兩邊擴散來判斷回文串。對于最長回文子串，就是這個意思：

for 0 <= i < len(s):找到以 s[i] 為中心的回文串更新答案

但是呢，我們剛才也說了，回文串的長度可能是奇數也可能是偶數，如果是 abba這種情況，沒有一個中心字符，上面的算法就沒轍了。所以我們可以修改一下：

for 0 <= i < len(s):找到以 s[i] 為中心的回文串找到以 s[i] 和 s[i+1] 為中心的回文串更新答案

3.代碼實現

string palindrome(string& s, int l, int r) {// 防止索引越界while (l >= 0 && r < s.size() && s[l] == s[r]) {// 向兩邊展開l--; r++;}// 返回以 s[l] 和 s[r] 為中心的最長回文串return s.substr(l + 1, r - l - 1); }

為什么要傳入兩個指針 l 和 r 呢？因為這樣實現可以同時處理回文串長度為奇數和偶數的情況：

for 0 <= i < len(s):# 找到以 s[i] 為中心的回文串palindrome(s, i, i)# 找到以 s[i] 和 s[i+1] 為中心的回文串palindrome(s, i, i + 1)更新答案

longestPalindrome完整代碼：

string longestPalindrome(string s) {string res;for (int i = 0; i < s.size(); i++) {// 以 s[i] 為中心的最長回文子串string s1 = palindrome(s, i, i);// 以 s[i] 和 s[i+1] 為中心的最長回文子串string s2 = palindrome(s, i, i + 1);// res = longest(res, s1, s2)res = res.size() > s1.size() ? res : s1;res = res.size() > s2.size() ? res : s2;}return res; }

• 至此，這道最長回文子串的問題就解決了，時間復雜度 O(N^2)，空間復雜度 O(1)。
• 值得一提的是，這個問題可以用動態規劃方法解決，時間復雜度一樣，但是空間復雜度至少要 O(N^2) 來存儲 DP table。這道題是少有的動態規劃非最優解法的問題。

二、判斷回文鏈表

1.問題描述

2. 分析

普通暴力求解就不說了！！！

• 借助二叉樹后序遍歷的思路，不需要顯式反轉原始鏈表也可以倒序遍歷鏈表，下面來具體聊聊。
• 對于二叉樹的幾種遍歷方式，我們再熟悉不過了：

void traverse(TreeNode root) {// 前序遍歷代碼traverse(root.left);// 中序遍歷代碼traverse(root.right);// 后序遍歷代碼 }

• 鏈表兼具遞歸結構，樹結構不過是鏈表的衍生。那么，鏈表其實也可以有前序遍歷和后序遍歷：

void traverse(ListNode head) {// 前序遍歷代碼traverse(head.next);// 后序遍歷代碼 }

• 這個框架有什么指導意義呢？如果我想正序打印鏈表中的val值，可以在前序遍歷位置寫代碼；反之，如果想倒序遍歷鏈表，就可以在后序遍歷位置操作：

/* 倒序打印單鏈表中的元素值 */ void traverse(ListNode head) {if (head == null) return;traverse(head.next);// 后序遍歷代碼print(head.val); }

• 說到這了，其實可以稍作修改，模仿雙指針實現回文判斷的功能：

3.代碼

// 左側指針 ListNode left;boolean isPalindrome(ListNode head) {left = head;return traverse(head); }boolean traverse(ListNode right) {if (right == null) return true;boolean res = traverse(right.next);// 后序遍歷代碼res = res && (right.val == left.val);left = left.next;return res; }

• 這么做的核心邏輯是什么呢？實際上就是把鏈表節點放入一個棧，然后再拿出來，這時候元素順序就是反的，只不過我們利用的是遞歸函數的堆棧而已。
  

當然，無論造一條反轉鏈表還是利用后續遍歷，算法的時間和空間復雜度都是 O(N)。下面我們想想，能不能不用額外的空間，解決這個問題呢？

4.優化

• 1、先通過「雙指針技巧」中的快慢指針來找到鏈表的中點：

ListNode slow, fast; slow = fast = head; while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next; } // slow 指針現在指向鏈表中點

• 2、如果fast指針沒有指向null，說明鏈表長度為奇數，slow還要再前進一步：

if (fast != null)slow = slow.next;

• 3、從slow開始反轉后面的鏈表，現在就可以開始比較回文串了：

ListNode left = head; ListNode right = reverse(slow);while (right != null) {if (left.val != right.val)return false;left = left.next;right = right.next; } return true;

至此，把上面 3 段代碼合在一起就高效地解決這個問題了，其中reverse函數很容易實現：

ListNode reverse(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre; }

• 算法總體的時間復雜度 O(N)，空間復雜度 O(1)，已經是最優的了。
• 我知道肯定有讀者會問：這種解法雖然高效，但破壞了輸入鏈表的原始結構，能不能避免這個瑕疵呢？
• 其實這個問題很好解決，關鍵在于得到p, q這兩個指針位置：

這樣，只要在函數 return 之前加一段代碼即可恢復原先鏈表順序：

p.next = reverse(q);

• 首先，尋找回文串是從中間向兩端擴展，判斷回文串是從兩端向中間收縮。
• 對于單鏈表，無法直接倒序遍歷，可以造一條新的反轉鏈表，可以利用鏈表的后序遍歷，也可以用棧結構倒序處理單鏈表。
• 具體到回文鏈表的判斷問題，由于回文的特殊性，可以不完全反轉鏈表，而是僅僅反轉部分鏈表，將空間復雜度降到 O(1)。

三、回文子串

1.問題描述

2.代碼

#include <bits/stdc++.h> using namespace std;int palindrome(string str,int l,int r) {int count = 0;while(l >= 0 && r < str.size() && str[l] == str[r]){count++;l--;r++;}return count; }int main() {string str;int ret = 0;while(cin>>str){for(int i = 0;i < str.size();i++){int num1 = palindrome(str, i, i);int num2 = palindrome(str, i, i + 1);ret += (num1 + num2);}cout<<ret<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的最长回文子串和回文链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。