algorithm - 最长回文子串自顶向下递归方法
问题描述
我正在尝试解决Leetcode 上最长的回文子串。我知道这个问题的解决方案,比如围绕中心展开或动态编程自下而上的方法。出于纯粹的教育目的,我想以自上而下的递归方式解决这个问题。我正在尝试找到类似于此处或此处描述的解决方案。(问题略有不同)。我有这个功能:
private (int Start, int End) Longest(string s, int i, int j)
它采用字符串+搜索的开始和结束位置。返回的元组是最长回文的开始和结束。我试图分成这些情况:
- if s[i] == s[j] 调查 Longest(s, i+1, j-1)
- 调查最长(s, i+1, j)
- 调查最长(s, i, j - 1)
- 从这三个中返回最长(返回的开始和结束之间的最大差异)
当然,我使用以元组 (int, int) 作为键(i 和 j 的值)的字典来记住所有计算结果,以便不再计算它们。
完整的代码如下,但是当我尝试修复算法时,经过几次迭代后它非常混乱。我相信创建代码不是很重要。
代码似乎返回了正确的结果,但在 Leetcode 上的 Time Limit Exceeded 上失败了。是否有正确的快速递归解决方案?我相信应该存在 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;
}
编辑:工作自下而上的解决方案(从geegsforgeegs复制):
public string LongestPalindrome(string s) {
if (s.Length == 0) return "";
var table = new bool[s.Length, s.Length];
var len = s.Length;
for (int i = 0; i < len; i++) {
table[i,i] = true;
}
var start = 0;
var max = 1;
for (int i = 0; i < len - 1; i++) {
if (s[i] == s[i + 1]) {
start = i;
max = 2;
table[i, i+1] = true;
}
}
for (int k = 3; k <= len; ++k) {
// Fix the starting index
for (int i = 0; i < len - k + 1; ++i)
{
// Get the ending index of substring from
// starting index i and length k
int j = i + k - 1;
// checking for sub-string from ith index to
// jth index iff str.charAt(i+1) to
// str.charAt(j-1) is a palindrome
if (table[i + 1, j - 1] && s[i] == s[j]) {
table[i,j] = true;
if (k > max) {
start = i;
max = k;
}
}
}
}
return s.Substring(start, max);
}
解决方案
这是 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]
推荐阅读
- rust - 如何从返回异步的 Vec 闭包中加入_all?
- google-apps-script - Quandl API 在 Google appscript 上返回 HTML 响应
- javascript - 画布绘制触摸未绘制
- python-3.x - 具有多个输入的 Python 字典列表搜索
- node.js - 需要帮助以解决 npm start 错误
- jaxb - 通过 WebServiceGatewaySupport 编组失败并出现 JAXBException: class
在此上下文中也不知道它的任何超类 - c# - 如何获取带有版本的操作系统安装补丁详细信息
- php - 在 WordPress 中为 body 标签添加自定义样式
- javascript - Puppeteer 按他的班级名称选择一个段落
- postgresql - 将 hasura 与 Google Cloud Run 和 Google Cloud SQL 结合使用