数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学Python3程序：查找具有相同左右旋转的最长子序列
在这个问题中，我们将找到给定字符串的最长子序列的长度，该子序列具有相同的左右旋转。
我们可以通过找到给定字符串的所有子序列并检查特定子序列是否具有相同的左右旋转来解决问题。另一种方法是利用观察结果，即如果字符串包含单个字符或交替字符且左侧为偶数，则字符串只能具有相同的左右旋转。
问题陈述 – 我们给定一个仅包含数字字符的字母字符串。我们需要找到字符串的最长子序列的大小，该子序列具有相同的左右旋转。
示例
输入
alpha = "700980503"
输出
4
解释 – 具有相同左右旋转的最长子序列是 '0000'。
输入
alpha = ‘19199019’
输出
6
解释 – 结果子序列是 '191919'。
输入
alpha = ‘13141115611171’
输出
9
解释 – 具有相同左右旋转的最长子序列是 '111111111'。
方法 1
在这种方法中，我们将找到给定字符串的所有子序列。之后，我们将使用 Python 数组切片来检查子序列是否具有相同的左右旋转。
算法
步骤 1 – 将 'maxLen' 初始化为 -1 以存储子序列的最大长度。
步骤 2 – 调用 getSubs() 函数以获取给定字符串的所有子序列。
步骤 2.1 – 在 getSubs() 函数中，将 'allSubs' 数组初始化为单个空字符串元素。
步骤 2.2 – 开始遍历字符串，并在 'temp' 变量中创建数组的副本。
步骤 2.3 – 遍历 'temp' 数组并将 'ch' 字符追加到 temp 数组的子序列中。之后，将新的子序列插入到 'allSubs' 数组中。
步骤 2.4 – 返回 'allSubs' 数组。
步骤 3 – 获取所有子序列后，遍历子序列数组。
步骤 4 – 使用 subseq[1:] + subseq[:1] 切片子序列以获取左旋转。同样，使用 subseq[str_len - 2:] + subseq[:str_len - 2] 切片子序列以获取右旋转。
步骤 5 – 如果左右旋转相同，则如果 maxLen 值小于子序列的长度，则更新 maxLen 值。
步骤 6 – 返回 'maxLen' 变量的值。
示例
def getSubs(alpha):
allSubs = ['']
for ch in alpha:
# Create a copy of the array containing all subsequences
temp = allSubs[:]
# Append character to each subsequence of the array to generate new subsequences
for subseq in temp:
allSubs.append(subseq + ch)
return allSubs
def maxSubSeqLen(alpha):
maxLen = -1
str_len = len(alpha)
allSubs = getSubs(alpha)
# Traverse all subsequences
for subseq in allSubs:
# check if the subsequence has the same left and right rotation
if subseq[1:] + subseq[:1] == subseq[str_len - 2:] + subseq[:str_len - 2]:
maxLen = max(maxLen, len(subseq))
# Return the answer
return maxLen
alpha = "1919019"
print("The maximum length of subsequence having the same left and right rotations is - ")
print(maxSubSeqLen(alpha))
输出
The maximum length of subsequence having the same left and right rotations is - 6
时间复杂度 – O(2N)，因为我们找到了给定字符串的所有子序列。
空间复杂度 – O(2N)，因为我们存储了给定字符串的所有子序列。
方法 2
在这种方法中，我们将使用基于问题输入和输出的观察结果。只有当字符串包含所有相同的字符或长度为偶数且包含交替字符时，字符串才能具有相同的左右旋转。
因此，我们将根据这两种条件找到最长的子序列。
算法
步骤 1 – 将 'maxLen' 变量初始化为 -1。
步骤 2 – 使用循环从 0 遍历到 9。此外，使用另一个嵌套循环从 0 遍历到 9。在这里，我们配对数字，例如 00、01、02、… 01、12、13、14、… 97、98、99 等。因此，我们将找到给定字符串中的数字对并获取子序列的最大长度。
步骤 3 – 将 'currMax' 和 'isSecond' 变量初始化为 0 以存储给定字符串中存在的数字对的总数，并跟踪在字符串中查找对的第一个或第二个字符以创建交替子序列。
步骤 4 - 开始遍历字符串。如果 'isSecond' 等于 0，并且字符等于 'p'，则将 'isSecond' 更改为 1 并将 'currMax' 值增加 1。
步骤 5 - 如果 'isSecond' 等于 1，并且字符等于 'q'，则将 'isSecond' 更改为 0 并将 'currMax' 值增加 1。
步骤 6 – 如果 p 和 q 不相同，并且 'currMax' 为奇数，则将其值减 1。
步骤 7 – 如果 'maxLen' 小于 'currMax' 变量的值，则更新 'maxLen' 的值。
步骤 8 – 返回 'maxLen' 值。
示例
def maxSubSeqLen(alpha):
# Length of the string
str_len = len(alpha)
maxLen = -1
# Travere the string
for p in range(10):
for q in range(10):
currMax, isSecond = 0, 0
# Find an alternate combination of p and q
for k in range(str_len):
# Finding the p
if (isSecond == 0 and ord(alpha[k]) - ord('0') == p):
isSecond = 1
# Increase the current value by 1
currMax += 1
# Finding q
elif (isSecond == 1 and ord(alpha[k]) - ord('0') == q):
isSecond = 0
# Increase the current value by 1
currMax += 1
# For odd length of resultant subsequence.
if p != q and currMax % 2 == 1:
# Decrease the value of currMax by 1
currMax -= 1
# Get maximum length
maxLen = max(currMax, maxLen)
# Return the answer
return maxLen
# Driver code
alpha = "700980503"
print("The maximum length of subsequence having the same left and right rotations is - ")
print(maxSubSeqLen(alpha))
输出
The maximum length of subsequence having the same left and right rotations is - 4
时间复杂度 – O(N*10*10) ~ O(N) 用于遍历字符串。
空间复杂度 – O(1)，因为我们不使用额外的空间。
第一种方法在时间上开销很大，因为我们找到了给定字符串的所有子序列。第二种方法是最佳方法之一，因为它具有最低的时间复杂度。程序员可以尝试查找具有相同左右旋转的最长子字符串以进行更多练习。
74 次查看
