Python3 获取相同字符串所需的最小旋转次数

在这个问题中，我们需要找出获取相同字符串所需的总旋转次数。解决这个问题的朴素方法是持续旋转字符串。如果我们找到相同字符串，我们可以打印出所需的旋转次数。

另外，其他方法会从字符串中提取子串，并使其等于原始字符串。之后，我们可以使用子串的长度来获取旋转次数。

问题陈述 - 我们已经给出了字符串str。我们需要找出获取相同字符串所需的总旋转次数。

示例

输入

str = "abab"

输出

2

解释 - 当我们将字符串左旋转两次，我们可以得到相同的字符串。

• 在第一次旋转中，字符串变为“baba”。

• 在第二次旋转中，字符串变为“abab”，与原字符串相等。

输入

str = ‘aaaa’

输出

4

解释 − 由于字符串的所有旋转都是相同的，所以我们需要总共4次旋转才能得到原始字符串。

输入

str = ‘abcd’

输出

4

说明 − 由于字符串的所有旋转都不同，我们需要旋转与字符串长度相等的次数。

方法1

在这种方法中，我们将从第p个索引到末尾取一个子字符串，然后从第0个索引到第p个索引开始。然后，我们将合并这两个字符串。如果合并后的字符串等于原始字符串，我们可以说需要p次旋转才能得到相同的字符串。

步骤

步骤1 − 使用循环将‘rotations’变量初始化为零，用于存储总的旋转次数。

步骤2 − 使用循环遍历字符串。

步骤3 − 从第p个索引开始取一个子字符串，同时取从第0个索引到第p个索引的子字符串。

步骤4 − 合并这两个子字符串。

步骤5 − 如果合并后的字符串等于alpha，用p更新‘rotations’变量的值并跳出循环。

步骤6 − 如果‘rotations’的值为零，返回字符串的长度。否则，返回‘rotations’的值。

示例

def totalRotations(alpha):
    rotations = 0  # to store total rotations
    length = len(alpha)  # string length
    # traverse the string
    for p in range(1, len(alpha) - 1):
        # if [p: length] + [0: p] is the same as [0: length], rotation found
        if (alpha[p: length] + alpha[0: p] == alpha):
            rotations = p
            break
#  If the string is not rotated at all, then return the length of the string
    if (rotations == 0):
        return length
    return rotations

if __name__ == '__main__':
    str = "abab"
    result = totalRotations(str)
    print("The number of rotations to get the same string are:", result)

输出

The number of rotations to get the same string are: 2

时间复杂度 − O(N^2)，因为我们使用循环来遍历字符串并获取其中的子串。

空间复杂度 − O(1)，因为我们不使用动态空间。

方法2

在这种方法中，我们将从第p个索引开始，取与N相等长度的旋转子串。如果它与原始字符串匹配，我们可以说实现原始字符串所需的最小旋转次数等于当前索引。

步骤

步骤1 − 将字符串与自身合并并存储在“tmp”变量中。

步骤2 − 开始遍历“tmp”字符串。

步骤3 − 从第p个索引开始获取旋转子串，其长度等于原始字符串的长度。

步骤4 − 如果“str”等于“substr”，则返回p。

步骤5 − 最后返回“len”。

示例

def totalRotations(str):
    # Merge string with itself
    tmp = str + str
    length = len(str)

    for p in range(1, length + 1):
        # get a substring of length equal to len and starting from the pth index of the tmp string
        substring = tmp[p: p+length]

        # If str and substring are equal, return p
        if str == substring:
            return p
    return len

if __name__ == '__main__':
    str = "efg"
    result = totalRotations(str)
    print("The number of rotations to get the same string are:", result)

输出

The number of rotations to get the same string are: 3

时间复杂度 − O(N^2) 因为我们在循环中获取了旋转的子串。

空间复杂度 − O(N) 因为我们将合并后的字符串存储到 ‘tmp’ 变量中。

我们学习了两种方法来获取原始字符串的总旋转次数。这两种方法都是通过获取特定长度的子串，合并它们，然后找到所需旋转的总数。