【leetcode】【剑指offer Ⅱ】019. 最多删除一个字符得到回文

问题描述：

• 给定一个非空字符串 s，请判断如果最多从字符串中删除一个字符能否得到一个回文字符串。

核心思路：

• 回文问题用双指针。
  • 递归处理问题，如果双指针对应的字符相等，则同时向中间移动（++l, --r）；但如果双指针对应的字符不相等且是第一次不相等，则考虑只移动左指针（++l）或只移动右指针（--r）。

代码实现：

• 代码实现如下：【直接递归，数据量不大，可以通过】

  class Solution
  {
  private:
      bool dfs(string& s, int l, int r, bool flag)
      {
          if(l > r) return true;
          if(s[l] == s[r])
              return dfs(s, l+1, r-1, flag);
          if(!flag) return false;
          return dfs(s, l, r-1, false) or dfs(s, l+1, r, false);
      }
  public:
      bool validPalindrome(string& s)
      {
          return dfs(s, 0, s.size()-1, true);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 另一版代码如下：【迭代比较，遇到不相等才调用一个同样操作的函数】

  class Solution
  {
  private:
      bool isValid(string& s, int lo, int hi)
      {
          while(lo < hi)
          {
              if(s[lo] != s[hi])
                  return false;
              ++lo, --hi;
          }
          return true;
      }
  public:
      bool validPalindrome(string& s)
      {
          int lo = 0, hi = s.size() - 1;
          while(lo < hi)
          {
              if(s[lo] != s[hi])// 第一次出错，就继续进入isValid，isValid做的事和这个函数的一样
                  return isValid(s, lo, hi-1) || isValid(s, lo+1, hi);
              ++lo, --hi;
          }
          return true;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26