---

博客主頁： [小????????] 本文專欄: C++

---

---

---

💯前言

• 判斷一個字符串是否為回文是編程中常見的問題。回文字符串是指從前往后讀與從后往前讀都一樣的字符串。例如，“abcdedcba” 就是回文，而 “abcde” 則不是。對于這類問題，我們可以采用多種不同的算法來解決。在本篇文章中，我們將分析四種不同的做法，并進行對比與優化，以幫助大家更好地理解如何判斷字符串是否為回文。
  C++ 參考手冊
  

---

💯題目描述

B2124 判斷字符串是否為回文

輸入一個字符串，判斷該字符串是否是回文。回文是指順讀和倒讀都一樣的字符串。

輸入格式：

輸入一行字符串，長度小于100。

輸出格式：

如果字符串是回文，輸出 yes；否則，輸出 no。

樣例：

輸入：

abcdedcba

輸出：

yes

💯方法一：我的第一種做法

思路

我的第一種做法是通過反轉字符串來判斷回文。首先，我們將原字符串反轉，然后與原字符串進行比較。如果反轉后的字符串與原字符串相等，則說明原字符串是回文。

代碼實現

#include <iostream>
#include <string>
using namespace std;int main() {string s;cin >> s;  // 輸入字符串int left = 0;int right = s.size() - 1;// 檢查字符串的前半部分是否與后半部分對稱while (left < right) {if (s[left] != s[right]) {cout << "no" << endl;  // 如果有不同字符，輸出noreturn 0;}left++;right--;}cout << "yes" << endl;  // 如果沒有不同字符，輸出yesreturn 0;
}

解析

1. 反轉字符串：通過雙指針方式，使用 left 和 right 兩個指針分別從字符串的兩端開始向中間移動，逐個比較字符。
2. 時間復雜度：O(n)，其中 n 是字符串的長度。我們最多需要遍歷字符串的前半部分，進行字符比較。
3. 空間復雜度：O(1)，僅使用了常數的空間來存儲指針 left 和 right。

💯方法二：我的第二種做法

思路

在我的第二種做法中，我嘗試使用了兩次循環，首先將字符串反轉到一個新的字符串 s2 中，然后通過逐字符對比 s2 和原字符串 s1 是否一致來判斷回文。

代碼實現

#include <iostream>
#include <string>
using namespace std;int main() {string s1, s2;while(cin >> s1) {s2.resize(s1.size());  for(int i = s1.size() - 1; i >= 0; i--) {s2[s1.size() - i - 1] = s1[i];}int temp = 1;for(int i = 0; i < s1.size(); i++) {if(s2[i] != s1[i]) {temp = 0;break;}}if(temp)cout << "yes" << endl;elsecout << "no" << endl;}return 0;
}

解析

1. 字符串反轉：首先創建一個 s2 字符串，并使用 for 循環反轉 s1 字符串的內容，存儲到 s2 中。
2. 回文判斷：然后通過逐個字符對比 s2 和 s1，如果遇到不同的字符，則輸出 no。
3. 存在問題：
   • s2 沒有預先調整大小： s2 在反轉前沒有設置大小，可能會導致內存越界。可以通過 resize 來調整其大小。
   • 邏輯錯誤：break 的位置存在問題，導致判斷邏輯不正確，跳出循環時判斷不夠精確。

改進建議

通過雙指針法可以優化空間使用，并且避免了額外的字符串存儲開銷。具體改進后我們會在后面介紹。

💯方法三：老師的第一種做法

思路

老師的第一種做法采用了雙指針法。這是一種非常高效的方法。通過兩個指針，分別從字符串的兩端開始，逐個比較字符，如果出現不同的字符，就可以直接返回 no，否則直到兩個指針相遇時，輸出 yes。

代碼實現

#include <iostream>
#include <string>
using namespace std;int main() {string s;cin >> s;  // 輸入字符串int left = 0;int right = s.size() - 1;while (left < right) {if (s[left] != s[right]) {cout << "no" << endl;  // 如果有不同字符，輸出noreturn 0;}left++;right--;}cout << "yes" << endl;  // 如果沒有不同字符，輸出yesreturn 0;
}

解析

1. 雙指針法：通過兩個指針 left 和 right 從字符串的兩端向中間逼近。每次比較 s[left] 和 s[right]，如果發現不相等，直接返回 no，否則繼續向中間推進。
2. 時間復雜度：O(n)，每次最多需要遍歷一次字符串的長度。
3. 空間復雜度：O(1)，只使用了常數空間來存儲兩個指針。

優點

1. 空間復雜度為 O(1)，避免了額外的空間開銷。
2. 效率高，每次只進行一次字符比較，比反轉字符串的方法更直接且高效。

💯方法四：老師的第二種做法

思路

老師的第二種做法使用了標準庫中的 reverse 函數，將字符串反轉后直接與原字符串進行比較。這是一種簡潔的做法，但其空間復雜度稍高，因為需要額外的存儲空間來保存反轉后的字符串。

代碼實現

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;int main() {string s;cin >> s;string t = s;reverse(t.begin(), t.end());  // 反轉字符串if (t == s) cout << "yes" << endl;elsecout << "no" << endl;return 0;
}

解析

1. 字符串反轉：利用 reverse 函數將字符串 s 反轉，并保存到 t 中。
2. 回文判斷：通過直接比較反轉后的字符串 t 和原字符串 s 是否相等來判斷回文。

優點

1. 代碼簡潔：通過標準庫函數，代碼更加簡潔和易懂。
2. 實現簡單：使用 reverse 可以減少手動反轉字符串的工作量。

缺點

1. 空間復雜度為 O(n)，因為需要額外的字符串 t 來存儲反轉后的字符串。

💯對比分析

1. 空間復雜度：

   • 我的第一種做法和老師的第一種做法都使用了 O(1) 空間，通過雙指針來直接判斷回文。
   • 我的第二種做法和老師的第二種做法需要額外的 O(n) 空間來存儲反轉后的字符串。

2. 時間復雜度：

   • 所有方法的時間復雜度均為 O(n)，其中 n 是字符串的長度。

3. 可讀性與簡潔性：

   • 我的第二種做法和老師的第二種做法通過反轉字符串，代碼簡單易懂。
   • 我的第一種做法和老師的第一種做法更加高效，避免了不必要的空間開銷。

💯擴展：空間優化和實際應用

在一些實際應用中，空間的使用往往是一個重要的考慮因素。如果我們能夠通過優化算法減少空間復雜度，將會使得程序更高效。雙指針法就是在空間優化方面的一個典型例子，它避免了反轉字符串時的額外存儲。

💯小結

本文通過分析四種不同的做法來判斷字符串是否為回文，比較了它們在空間和時間復雜度上的表現。通過這幾種做法，我們可以發現，雙指針法在空間和時間上的優勢較為明顯，是最為推薦的解決方案。當然，對于小規模的問題，使用字符串反轉的做法也不失為一種簡潔高效的選擇。

希望本篇文章能夠幫助大家更好地理解字符串回文判斷的不同做法，并能夠根據實際問題選擇合適的算法。

---

---