首页 文章

最长的回文子串自上而下的递归方法

提问于
浏览 次
2

我想在Leetcode上解决Longest palindromic substring . 我知道这个问题的解决方案，如围绕中心扩展或dynamic programming bottom up approach . 出于纯粹的教育目的，我想以自上而下的递归方式解决这个问题 . 我试图找到类似于描述here或here的解决方案 . （问题略有不同） . 我有这个功能：

private (int Start, int End) Longest(string s, int i, int j)

它采用搜索的字符串开始和结束位置 . 返回的元组是最长的回文的开始和结束 . 我试图分裂成这些情况：

  • 如果s [i] == s [j]调查最长（s，i 1，j-1）

  • 调查最长（s，i 1，j）

  • 调查时间最长（s，i，j - 1）

  • 从这三个中返回最长（返回的开始和结束之间的最大差异）

当然我使用带有tuple（int，int）的Dictionary作为键（i和j的值）来记住所有计算结果，以便不再计算它们 .

完整代码如下，但在我尝试修复算法后几次迭代后它非常混乱 . 我相信concreate代码不是很重要 .

代码似乎返回正确的结果但在Leetcode上超过时间限制时失败 . 有正确的快速递归解决方案吗？我相信应该存在DP自下而上的解决方案 .

码：

private readonly IDictionary<(int, int), (int, int)> _mem = new Dictionary<(int, int), (int, int)>();

private (int Start, int End) Longest(string s, int i, int j) {
    if (i >= j) {
        return (i, j);
    }

    if (_mem.TryGetValue((i, j), out var ret)) {
        return ret;
    }

    var newI = i + 1;
    var newJ = j - 1;

    ValueTuple<int, int> removingTwo;

    if (s[i] == s[j])
    {
        removingTwo = Longest(s, newI, newJ);

        if (removingTwo.Item1 == newI && removingTwo.Item2 == newJ) {
            removingTwo.Item1--;
            removingTwo.Item2++;
        }
    }
    else {
        removingTwo = (1, 0);
    }

    var removingFirst = Longest(s, newI, j);
    var removingLast = Longest(s, i, newJ);  

    var mT = removingTwo.Item2 - removingTwo.Item1;
    var mF = removingFirst.End - removingFirst.Start;
    var mL = removingLast.End - removingLast.Start;

    var max = Math.Max(mT, mF);
    max = Math.Max(max, mL);

    ValueTuple<int, int> retVal;

    if (max == mT) retVal = removingTwo;
    else if (max == mF) retVal = removingFirst;
    else retVal = removingLast;

    _mem.Add((i, j), retVal);

    return retVal;

}
algorithm recursion dynamic-programming longest-substring

1 回答

  • 1

    这是Python中一个递归LeetCode测试的递归方法 . 可能他们正在寻找恒定的太空解决方案 .

    f(i, k) 返回 (l, j) ，长度为 l 的最大元组及其起始索引 j . 在这个例子中 max 正在查看返回元组的第一个元素，即 l ，即回文的长度 .

    def longestPalindrome(self, s):
  def f(i, k):
    return max(
      # next iteration
      f(i - 1, 1) if k < 2 and i > 0 else (-1,-1),
      f(i - 1, 2) if k < 2 and i > 0 and s[i-1] == s[i] else (-1, -1),

      # a larger palindrome than this one
      f(i - 1, k + 2) if i > 0 and i + k < len(s) and s[i-1] == s[i + k] else (-1, -1),

      # this one
      (k, i)
    )

  (l, j) = f(len(s) - 1, 1)
  return s[j:j+l]
    回复于

相关问题