用 Python 中的子字符串生成回文
pythonserver side programmingprogramming
假设我们有一个字符串 s，我们需要对 s 的子字符串进行查询。对于每个查询查询 [i]，有三个部分 [left, right, k]，我们可以重新排列子字符串 s[left], ..., s[right]，然后选择其中最多 k 个替换为任意小写英文字母。如果经过上述操作后子字符串有可能是回文，则查询结果为真。否则为假。我们必须找到一个数组 answer[]，其中 answer[i] 是第 i 个查询 queries[i] 的结果。
例如，如果输入是 “abcda”，queries 类似于 [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]，则输出将是 [true, false, false, true, true]
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个名为solve的方法，它将采用dp矩阵和q。这将像下面的 − 一样工作
- l := q[0], r := q[1], k := q[2], 然后将 l 和 r 增加 1, one := 0
- 对于 i 在 0 到 25 的范围内
- one := one + (dp[r, i] – dp[l – 1, i]) mod 2
- 当 one / 2 的整数除法 <= k 时返回 true，否则返回 false
- 定义另一个名为 makeDP() 的方法，它将采用 dp 矩阵和 s，这将像下面的 − 一样工作
- 对于 i 在 0 到 s 的长度的范围内
- 对于 j 在 0 到 25 的范围内
- dp[i, j] := dp[i – 1, j]
- 将 dp[i, s[i] 的 ASCII – ‘a’] 增加 1
- 对于 j 在 0 到 25 的范围内
- 主要方法将类似于 −
- n := 字符串 s 的大小，s := “ ” 连接 s
- dp := 阶数为 (n + 1) x 26 的矩阵，并用 0 填充
- 调用 makeDP(dp, s)
- res := 大小与 q 长度相同的数组，并用 false 填充
- 对于 i，范围为 0 到 q 的长度 – 1
- res[i] := resolve(dp, q[i])
- return res
示例(Python)
让我们看看以下实现以获得更好的理解 −
class Solution(object):
def solve(self,dp,q):
l = q[0]
r = q[1]
k = q[2]
r+=1
l+=1
#arr = [ 0 for i in range(26)]
one = 0
for i in range(26):
one += (dp[r][i]-dp[l-1][i])%2
return one//2<=k
def make_dp(self,dp,s):
for i in range(1,len(s)):
for j in range(26):
dp[i][j] = dp[i-1][j]
dp[i][ord(s[i])-ord('a')]+=1
def canMakePaliQueries(self, s, q):
n = len(s)
s = " "+s
dp = [[0 for i in range(26)] for j in range(n+1)]
self.make_dp(dp,s)
res = [False for i in range(len(q))]
for i in range(len(q)):
res[i] = self.solve(dp,q[i])
return res
ob = Solution()
print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))
输入
"abcda" [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出
[True, False, False, True, True]
