Python程式：查詢獲得實際字串所需的最少旋轉次數？

---

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

考慮這樣一種情況：一個字串向右旋轉一定次數。目標是找到將字串轉換回其原始形式所需的旋轉次數最少。透過解決這個問題，我們可以更多地瞭解字串的結構並訪問有用的資訊。

本文將探討兩種方法來確定將旋轉後的字串轉換回原始字串所需的最少旋轉次數。我們將使用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中的這個問題。透過掌握這些方法，您現在可以計算從給定字串中提取目標字串所需的最小旋轉次數。