数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找最长的“很棒”子字符串
假设我们有一个数字字符串s。众所周知，“很棒”的子字符串是s的一个非空子字符串，我们可以对其进行任意次交换以使其成为回文。我们必须找到s的最长“很棒”子字符串的长度。
因此，如果输入类似于s = "4353526"，则输出将为5，因为"35352"是最长的“很棒”子字符串。我们可以将“35253”变成回文。
为了解决这个问题，我们将遵循以下步骤：
n := 0
pos_map := 一个映射，其中包含键0以及对应的值s的大小
max_len := 1
对于范围从s的大小-1到0，递减1的i，执行以下操作：
n := n XOR (2^s[i])
如果n存在于pos_map中，则：
max_len := max_len和pos_map[n]-i中的最大值
对于范围从0到9的j，执行以下操作：
m := n XOR 2^j
如果m存在于pos_map中，则：
max_len := max_len和pos_map[m]-i中的最大值
如果n不在pos_map中，则：
pos_map[n] := i
返回max_len
示例
让我们看看下面的实现以更好地理解
def solve(s):
n = 0
pos_map = {0:len(s)}
max_len = 1
for i in range(len(s)-1, -1, -1):
n = n ^ (1 << int(s[i]))
if n in pos_map:
max_len = max(max_len, pos_map[n]-i)
for j in range(10):
m = n ^ (1 << j)
if m in pos_map:
max_len = max(max_len, pos_map[m]-i)
if n not in pos_map:
pos_map[n] = i
return max_len
s = "4353526"
print(solve(s))输入
"4353526"
输出
5
更新于: 2021年10月6日
439 次查看
广告