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

---

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

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

问题陈述− 我们给定字符串str。我们需要找到获得相同字符串所需旋转的总数。

示例

输入

str = "abab"

输出

2

解释− 当我们对字符串进行2次左旋转时，我们可以得到相同的字符串。

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

• 第二次旋转后，字符串变为“abab”，等于原始字符串。

输入

 str = ‘aaaa’

输出

4

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

输入

 str = ‘abcd’

输出

4

解释− 由于字符串的所有旋转都不同，因此我们需要等于字符串长度的旋转次数。

方法一

在这种方法中，我们将从第p个索引到结尾处获取一个子字符串，并从第0个索引到第p个索引处开始。之后，我们将合并两个字符串。如果结果字符串等于原始字符串，我们可以说获得相同字符串所需的总旋转次数为p。

算法

步骤1− 用零初始化“旋转”变量以存储总旋转次数。

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

步骤3− 获取从第p个索引开始的子字符串。另外，获取从第0个索引到第p个索引的子字符串。

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

步骤5− 如果合并后的字符串等于alpha，则将“旋转”变量的值更新为p并中断循环。

步骤6− 如果“旋转”的值为零，则返回字符串的长度。否则，返回“旋转”。

示例

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)，因为我们不使用动态空间。

方法二

在这种方法中，我们将获取从第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”变量中。

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