回文串算法题

回文串是一个正着读和反着读顺序一样的字符串。aba 是回文串abba 是回文串abc 不是回文串。回文串的题目都要使用一个基本的逻辑就是判断当前这个字符串是不是回文串。以 c 为例代码如下。这种方法也可以称为双指针法两个指针从字符串的两端向中间遍历每个字符如果中间发现两个字符不相同则不是回文字符串遍历到最后说明是回文串。bool isPalindrome(const string s) { int len s.size(); if (len 1) { return true; } int left 0; int right len - 1; //决策使用还是就看有没有必要在这里没有必要所以使用 while (left right) { if (s[left] ! s[right]) { return false; } left; right--; } return true; }双指针法在其它数据结构题目中也会用到比如链表中会用到快慢指针也属于双指针。快速排序算法中给选中的数据找到合适的位置也会使用两个指针从两边向中间对数据进行遍历也属于双指针。判断回文串也可以使用从中间向两边的方法使用这种方法时首先需要判断字符串的长度是奇数还是偶数如果是奇数的话那么两个指针从中间的位置开始向两边遍历偶数的话两个指针分别从中间两个元素的位置开始遍历。没有特殊要求的话优先选用从两边向中间的方式来判断一个字符串是不是回文串。1 验证回文串leetcode验证回文串题目要求判断给定的字符串是不是回文串如果是回文串则返回 true如果原字符串不是回文串那么最多可以删除一个字符如果删除一个字符之后的字符串是回文串那么返回 true否则返回 false。1.1 基础算法1判断原字符串是不是回文串是回文串返回 true否则执行第 2 步2遍历字符串的每个字符分别将每个字符删除判断删除字符之后的字符串是不是回文串。如果是回文串则返回 true停止遍历如果字符遍历结束则返回 false。这种算法的时间复杂度是 O(n 的平方)偏大所以优先选用第二种方法第二种算法的时间复杂度是 O(n)。1.2 双指针动态判断1使用双指针从两边向中间遍历每个字符2如果遍历到两个字符不相等则讨论如下两种情况① 删除左边的字符判断子串是不是回文串是的话则返回 true② 删除右边的字符判断子串是不是回文串是的话返回 true如果两种情况都不是回文串那么返回 false。3如果字符串遍历结束都满足回文串的要求则返回 trueclass Solution { public: bool validPalindrome(string s) { int len s.size(); int left 0; int right len - 1; bool result true; while (left right) { if (s[left] ! s[right]) { if (isPalindrome(s.substr(left 1, right - left))) { return true; } if (isPalindrome(s.substr(left, right - left))) { return true; } return false; } left; right--; } return true; } bool isPalindrome(const string s) { int len s.size(); if (len 1) { return true; } int left 0; int right len - 1; while (left right) { if (s[left] ! s[right]) { return false; } left; right--; } return true; } };2 最长回文子串leetcode最长回文子串一个字符串 s找到 s 中最长的回文子串。2.1 动态规划将所有的子串的情况都遍历到在遍历的过程中判断子串是不是回文串如果是回文串并且长度比已有的回文串长的话那么就更新结果。属于动态规划算法。这个算法的事件复杂度是 O(n 的平方)时间复杂度较高在 leetcode 上运行时会超时。class Solution { public: string longestPalindrome(string s) { int size s.size(); for (int i 0; i size; i) { for (int j i; j size; j) { if (isPalindrome(s.substr(i, j - i 1))) { if (j - i 1 max_length) { max_length j - i 1; max_str s.substr(i, j - i 1); } } } } return max_str; } private: bool isPalindrome(string s) { int size s.size(); int i 0; int j size - 1; while (i j) { if (s[i] ! s[j]) { return false; } i; j--; } return true; } private: int max_length 0; string max_str; };这个题目要找的是最长回文子串我们能想到 j 的遍历从大向小遍历。这样遍历的话就是先遍历长度大的字符串再遍历长度小的字符串。当第一个遍历到一个字符串是回文串那么这个回文串就是长度最大的回文串就可以直接返回。从小向大进行遍历当遍历到这个字符串是回文串的时候仍然不能返回因为不能确定这个字符串是不是长度最大的回文串需要将所有情况都遍历完毕才能确定最大的回文字符串。再进一步思考我们可以以子串的长度作为遍历的依据长度从大到小进行遍历。如下是使用c语言实现的算法。char ret[1001] {\0}; char* longestPalindrome(char* s) { int length strlen(s); if (length 1) { return s; } memset(ret, 0, 1001); for (int len length; len 1; len--) { for (int i 0; i length; i) { if (i len - 1 length) { break; } int start_index i; int end_index i len - 1; if (isPalindrome(s, start_index, end_index)) { int index 0; for (int i start_index; i end_index; i) { ret[index] s[i]; index; } return ret; } } } return NULL; } int isPalindrome(char *s, int start_index, int end_index) { while (start_index end_index) { if (s[start_index] ! s[end_index]) { return 0; } start_index; end_index--; } return 1; }官方题解中也是遍历了子串的长度但是是从小到大进行遍历的同时还记录了已经遍历过的子串的结果。当判断长度较大的字符串是不是回文串时可以直接基于历史记录来做判断。这也是动态规划常用的思路就是在遍历的过程中记录历史信息这样在后边的遍历中可以直接使用已经记录的历史信息。官方题解中正因为长度是从小到大进行遍历的所以在遍历的时候判断字符串是不是回文串的时候可以使用历史信息进行判断。因为 s[i][j] 比 s[i 1][j - 1] 的长度要大后者是不是回文串已经是确定的。2.2 中心扩展法leetcode 官方题解中提供了另外一种方法中心扩展法。这个问题的多种算法之间的区别就是遍历的对象不一样1两级遍历遍历字符串的索引2两级遍历一级遍历子串的长度一级遍历字符串的索引3中心扩展法也是遍历字符串的索引不过在计算逻辑上是把索引当成了要遍历的子串的中心class Solution { public: string longestPalindrome(string s) { int size s.size(); int start 0; int end 0; for (int i 0; i size; i) { int left1 i; int right1 i; int left2 i; int right2 i 1; // 从中心向两边扩展要考虑两种情况 // 奇数的情况偶数的情况 centerExpand(s, left1, right1); centerExpand(s, left2, right2); if (right1 - left1 end - start) { start left1; end right1; } if (right2 - left2 end - start) { start left2; end right2; } } return s.substr(start, end - start 1); } void centerExpand(string s, int left, int right) { while (left 0 right s.size() s[left] s[right]) { left--; right; } // 循环退出说明最后一个索引不满足回文串的情况 // 要么是 left 和 right 越界了要么是当前这两个字符不相等 // 这两种情况下left 需要 , right 需要 -- left; right--; } };3 分割回文子串leetcode分割回文子串本文用基础的算法去思考的话很难思考下去遇到这种情况一般要考是不是可以使用递归算法。第一个想出这种解法的人绝对值得敬佩。class Solution { public: vectorvectorstring partition(string s) { partitionHelper(s, 0); return result_; } void partitionHelper(const string s, int start_index) { int len s.size(); if (start_index len) { result_.push_back(one_instance_); return; } for (int i start_index; i len; i) { if (isPalindome(s, start_index, i)) { one_instance_.push_back(s.substr(start_index, i - start_index 1)); partitionHelper(s, i 1); one_instance_.pop_back(); } } } bool isPalindome(const string s, int start, int end) { if (start end) { return true; } if (flag[start][end] 1) { return true; } if (flag[start][end] -1) { return false; } int tmp_start start; int tmp_end end; while (tmp_start tmp_end) { if (s[tmp_start] ! s[tmp_end]) { flag[tmp_start][tmp_end] -1; flag[start][end] -1; return false; } tmp_start; tmp_end--; } flag[start][end] 1; return true; } private: int flag[20][20] {0}; vectorvectorstring result_; vectorstring one_instance_; };