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”變數中。

我們學習了兩種方法來獲得原始字串的總旋轉次數。兩種方法都獲取特定長度的子字串，將它們合併，並找到所需的總旋轉次數。