数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中从子字符串生成回文
假设我们有一个字符串 s，我们需要对 s 的子字符串进行查询。对于每个查询 queries[i]，都有三个部分 [left, right, k]，我们可以重新排列子字符串 s[left]，…，s[right]，然后选择最多 k 个字符替换为任何小写英文字母。如果子字符串在上述操作后可以成为回文，则查询结果为 true。否则为 false。我们需要找到一个数组 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’ 的 ASCII 值] 加 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] := solve(dp, q[i])
- 返回 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]
更新于: 2020-04-30
121 次查看
广告