C++实现字符串子串回文判断的多种方法与优化策略

我来帮你解决这个判断子串是否为回文串的问题。这是一个经典的字符串处理问题，有多种实现方法。 ## 🎯 问题分析 我们需要判断字符串 `s` 中从索引 `left` 到 `right`（包含两端）的子串是否是回文串。回文串的特点是正读和反读都相同。 ## 📝 解决方案 ### 方法1：双指针法（推荐） 这是最直观和高效的方法，时间复杂度 O(n)，空间复杂度 O(1)。 ```cpp #include <iostream> #include <string> using namespace std; int main() { string s; int left, right; // 读取输入 getline(cin, s); cin >> left >> right; // 双指针判断回文 bool isPalindrome = true; int i = left, j = right; while (i < j) { if (s[i] != s[j]) { isPalindrome = false; break; } i++; j--; } // 输出结果 if (isPalindrome) { cout << "yes" << endl; } else { cout << "no" << endl; } return 0; } ``` ### 方法2：使用字符串反转 这种方法更简洁，但需要额外的空间。 ```cpp #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; int left, right; getline(cin, s); cin >> left >> right; // 提取子串 string substring = s.substr(left, right - left + 1); string reversed = substring; reverse(reversed.begin(), reversed.end()); // 判断是否相等 if (substring == reversed) { cout << "yes" << endl; } else { cout << "no" << endl; } return 0; } ``` ## 🔍 关键概念解释 ### 1. **回文串定义** - 正读和反读都相同的字符串 - 例如："aba", "racecar", "a" 都是回文串 - 空字符串通常也被认为是回文串 ### 2. **索引范围** - C++ 字符串索引从 0 开始 - `left` 和 `right` 都是包含在判断范围内的 - 子串长度 = `right - left + 1` ## ⚠️ 边界情况处理 在实际开发中，需要考虑以下边界情况： ```cpp #include <iostream> #include <string> using namespace std; bool isPalindromeSubstring(const string& s, int left, int right) { // 输入验证 if (left < 0 || right >= s.length() || left > right) { return false; // 或根据需求抛出异常 } // 双指针判断 while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } int main() { string s; int left, right; // 使用 getline 读取可能包含空格的字符串 getline(cin, s); // 读取整数 if (!(cin >> left >> right)) { cout << "输入格式错误" << endl; return 1; } // 调用函数判断 if (isPalindromeSubstring(s, left, right)) { cout << "yes" << endl; } else { cout << "no" << endl; } return 0; } ``` ## 📊 方法比较 | 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | |------|------------|------------|------|------| | 双指针法 | O(n) | O(1) | 内存效率高，速度快 | 代码稍长 | | 字符串反转 | O(n) | O(n) | 代码简洁易懂 | 需要额外内存 | ## 💡 开发建议 1. **输入验证**：始终验证输入的有效性，特别是索引范围 2. **函数封装**：将核心逻辑封装成函数，提高代码复用性 3. **性能考虑**：对于大数据量，双指针法更优 4. **代码可读性**：添加适当的注释，特别是边界条件的处理 5. **测试用例**：编写测试用例覆盖各种情况： - 空字符串 - 单个字符 - 奇数长度回文 - 偶数长度回文 - 非回文字符串 - 索引越界情况 ## 🚀 进阶优化 如果需要频繁查询不同子串是否为回文，可以考虑使用动态规划预处理： ```cpp #include <iostream> #include <string> #include <vector> using namespace std; class PalindromeChecker { private: vector<vector<bool>> dp; string s; public: PalindromeChecker(const string& str) : s(str) { int n = s.length(); dp.resize(n, vector<bool>(n, false)); // 动态规划预处理 for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (i == j) { dp[i][j] = true; } else if (i + 1 == j) { dp[i][j] = (s[i] == s[j]); } else { dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; } } } } bool isPalindrome(int left, int right) { if (left < 0 || right >= s.length() || left > right) { return false; } return dp[left][right]; } }; int main() { string s; getline(cin, s); PalindromeChecker checker(s); int left, right; while (cin >> left >> right) { if (checker.isPalindrome(left, right)) { cout << "yes" << endl; } else { cout << "no" << endl; } } return 0; } ``` 这种方法预处理时间复杂度 O(n²)，但每次查询只需要 O(1) 时间，适合需要多次查询的场景。 ######[AI写代码神器 | 1414点数解答 | 2026-04-11 14:57:07]