我无法用python进行编程。
请帮帮忙。
我的思路是将初始计数器保持为1(即使一个字母完全不同的单词在默认情况下也有1)。
然后在字母中为每1次匹配添加2次
示例输入:“信函”
示例输出:5#(1(默认为+2( 2"t"s) +2( 2"e"s))
发布于 2022-12-04 12:22:36
您可以使用此代码计算最长子字符串的长度,该子字符串可以重新排列以形成回文:
def longestSubstring(s: str):
# To keep track of the last
# index of each xor
n = len(s)
index = dict()
# Initialize answer with 0
answer = 0
mask = 0
index[mask] = -1
# Now iterate through each character
# of the string
for i in range(n):
# Convert the character from
# [a, z] to [0, 25]
temp = ord(s[i]) - 97
# Turn the temp-th bit on if
# character occurs odd number
# of times and turn off the temp-th
# bit off if the character occurs
# even number of times
mask ^= (1 << temp)
# If a mask is present in the index
# Therefore a palindrome is
# found from index[mask] to i
if mask in index.keys():
answer = max(answer,
i - index[mask])
# If x is not found then add its
# position in the index dict.
else:
index[mask] = i
# Check for the palindrome of
# odd length
for j in range(26):
# We cancel the occurrence
# of a character if it occurs
# odd number times
mask2 = mask ^ (1 << j)
if mask2 in index.keys():
answer = max(answer,
i - index[mask2])
return answer该算法基本上是O(N*26)。XOR基本上检查某个字符的数量是偶数还是奇数。对于字符串中的每个字符,每个字符都有一个特定的异或序列,它告诉您哪些字符出现了奇数时间,哪些字符出现了偶数次。如果在过去已经遇到过相同的序列,那么您知道您已经找到了一个回文,因为您已经回到了在XOR序列中开始的位置--也就是在这个点和起点之间出现的每个字符的偶数。如果字符串中的两个点之间出现的每个字符都是偶数,那么您可以在它们之间形成一个回文。奇数长度检查只是检查回文的特例,回文的长度为奇数。如果一个字符出现奇数次,它就会依次假装,它只是假设出现偶数次,以处理字符在奇数长度回文中间的特殊情况。
编辑:这里是指向原始代码和解释的链接。
https://stackoverflow.com/questions/74674638
复制相似问题