Python程式：找到取得實際字串所需的最小旋轉次數？

了解如何有效地處理字串是一項基本的程式設計任務，可以顯著提高程式碼的效能。找到從旋轉的弦產生所需弦所需的最少旋轉次數是弦操作中的一個有趣的挑戰。文字處理、密碼學和資料壓縮等情況經常涉及這個問題。

考慮字串向右旋轉一定量的情況。目標是找到將字串轉回其原始形式所需的最少旋轉次數。透過找到該問題的解決方案，我們可以了解有關字串結構的更多資訊並獲取有用的信息。

本文將研究兩種方法，用於確定從旋轉字串傳回原始字串所需的最少旋轉次數。 Python 是一種靈活且廣受歡迎的程式語言，以其可讀性和易用性而聞名，將用於將這些技術付諸實踐。

方法

要在Python中搜尋獲得實際字串的最小旋轉次數，我們可以遵循兩種方法 -

• 利用蠻力。

• 在使用者定義函數中使用 while 迴圈。

讓我們研究一下這兩種方法 -

方法 1：利用蠻力

使用強力方法將第一個字串旋轉所有可能的位置，然後將第二個字串與旋轉後的第一個字串進行比較。我們透過迭代所有可行的旋轉來追蹤獲得第二個字串所需的最小旋轉次數。循環結束後，如果最小旋轉變數仍然是無限大，則不可能透過旋轉第一串來獲得第二串。如果沒有，我們返回所需的最少旋轉次數。此方法的時間複雜度為 O(n^2)，其中 n 為第一個字串的長度。

演算法

在Python中搜尋最小旋轉次數以獲得實際字串的步驟如下 -

第 1 步- 建立一個以兩個字串作為輸入的函數。

第 2 步- 建立一個初始值為無窮大的變量，以追蹤所需的最小旋轉次數。

第 3 步- 從 0 到第一個字串的長度，迭代可能的值。

第 4 步- 第一個字串應按目前索引位置旋轉。這驗證了第二個字串和旋轉後的字串是否相等。如果是這樣，請將變數的值變更為目前最小值和目前索引之間的最小值。

第 5 步− 如果最小旋轉變數仍設為無窮大，則傳回 -1（表示透過旋轉第一個字串來檢索第二個字串是不可行的）。

第 6 步- 如果沒有，則傳回最小旋轉變數。

範例

def min_rotations_bf(s1, s2):
   min_rotations = float('inf')

   for i in range(len(s1)):
      rotated = s1[i:] + s1[:i]
      if rotated == s2:
         min_rotations = min(min_rotations, i)

   if min_rotations == float('inf'):
      return -1
   else:
      return min_rotations


# Example usage
s1 = "program"
s2 = "grampro"
bf_result = min_rotations_bf(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations (Brute Force):", bf_result)

輸出

String 1: program
String 2: grampro
Minimum rotations (Brute Force): 3

方法 2：在使用者定義函數中使用 while 迴圈

有效的方法是使用連接的字串來驗證第二個字串是否存在，而不是進行明確的字串旋轉。如果由於兩個字串的長度不同而無法透過第一個字串的旋轉來檢索第二個字串，我們將傳回 -1。透過判斷第二個字串是否是連接字串的子字串，我們可以計算出需要旋轉多少次才能將第二個字串與第一個字串分開。為了確定最少的旋轉次數，如果發現第二個字串作為子字串，我們計算索引並將其除以第一個字串的長度。此方法的時間複雜度為O(n)，其中n是第一個字串的長度。

演算法

在Python中搜尋最小旋轉次數以獲得實際字串的步驟如下 -

第 1 步- 建立一個以兩個字串作為輸入的函數。

第 2 步- 如果兩個字串的長度不相等，則傳回 -1（因為無法透過旋轉第一個字串來獲得第二個字串）。

第 3 步- 透過將第一個字串與其自身連接來建立臨時字串。

第4 步- 如果第二個字串是臨時字串的子字串，則傳回所需的最低旋轉次數，作為臨時字串中第二個字串的索引除以第一個字串的長度.

第 5 步− 如果不是，則回傳 -1。

範例

def min_rotations_efficient(s1, s2):
   if len(s1) != len(s2):
      return -1

   rotations = 0
   n = len(s1)

   # Check for left rotations
   while rotations < n:
      if s1 == s2:
         return rotations
      s1 = s1[1:] + s1[0]
      rotations += 1

   # Check for right rotations
   s1 = s1[-1] + s1[:-1]
   rotations = 1

   while rotations <= n:
      if s1 == s2:
         return rotations
      s1 = s1[-1] + s1[:-1]
      rotations += 1

   return -1
# Example usage
s1 = "program"
s2 = "grampro"
efficient_result = min_rotations_efficient(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations ", efficient_result)

輸出

String 1: program
String 2: grampro
Minimum rotations  3

結論

在本文中，我們研究了兩種計算將給定字串轉換為另一個字串所需的最小旋轉次數的方法。第二種方法使用連接的字串來檢查第二個字串是否存在，而強力方法則將第一個字串旋轉每個可行的位置數。人們可以根據輸入的大小和所需的效率選擇最佳策略來解決 Python 中的這個問題。由於掌握了這些方法，您現在可以計算從給定字串中提取目標字串所需的最低旋轉次數。

以上是Python程式：找到取得實際字串所需的最小旋轉次數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！