將字串轉換為另一個字串所需的最小運算元

---

給定兩個字串 A 和 B，任務是將字串 A 轉換為字串 B（如果可能）。你只能執行一種操作，即從 A 中取出任何字元並將其插入到開頭。檢查是否可以轉換字串。如果是，則輸出轉換所需的最小運算元。

輸入輸出場景

假設我們有兩個字串 A 和 B，其值分別為“ABD”和“BAD”，將第一個字串轉換為第二個字串所需的操作是 1，即交換前兩個字元。

輸入

A = "ABD", B = "BAD"

輸出

1

考慮另一個場景

輸入

A = "EACBD", B = "EABCD"

輸出

3

將 A 轉換為 B 所需的操作是：

• 取 B 並放在前面，EACBD => BEACD

• 取 A 並放在前面，BEACD => ABECD

• 取 E 並放在前面，ABECD => EABCD

Python 實現

以下是 Python 實現

示例

def transformString(A, B):
    if len(A) != len(B):
        return -1    
    count = 0
    i = len(A) - 1
    j = len(B) - 1
    
    while i >= 0 and j >= 0:
        if A[i] == B[j]:
            i -= 1
            j -= 1
        else:
            count += 1
            i -= 1    
    return count
A = "Hello Welcome to Tutorialspoint    "
B = "Tutorialspoint simply easy learning"
print("Operations Required: ", transformString(A, B))  

A = "EACBD"
B = "EABCD"
print("Operations Required: ", transformString(A, B)) 

輸出

Operations Required:  35
Operations Required:  3

方法

讓我們透過除錯上述程式來了解所採用的方法。

• 該函式首先確定 A 和 B 的長度是否相等。如果長度不相等，則函式返回 -1，因為無法透過在開頭新增字母來將 A 更改為 B。

• 當 A 和 B 都具有相同的長度時，函式初始化兩個指標 i 和 j，它們分別指向 A 和 B 的末尾，以及一個變數 count 為 0。

• 之後，函式開始一個 while 迴圈，只要 i 和 j 都非負，該迴圈就會繼續執行。

• 在 while 迴圈內，函式檢查 A[i] 處的字元是否等於 B[j] 處的字元。如果它們相等，則函式將 i 和 j 都遞減 1，有效地跳過這些字元。

• 如果字元不相等，則函式將 count 遞增 1 並將 i 遞減 1，有效地將 A[i] 處的字元“插入”到 A 的開頭。

• 然後，函式確定 while 迴圈終止後 j 是否為負。如果是，則 B 中的所有字元都已與其在 A 中的等效項匹配，並且 count 的值反映了將 A 更改為 B 所需的最小插入次數。函式返回 count。

• 如果 j 不是負數，則無法透過在前面新增字元來將 A 更改為 B，因為 B 仍然包含未匹配的字元。當轉換不可能時，函式返回 -1。

Java 實現

以上程式碼的 Java 實現

示例

import java.util.*;

public class Demo{
   public static int transformString(String A, String B) {
   if (A.length() != B.length()) {
      return -1;
   }
   int count = 0;
   int i = A.length() - 1;
   int j = B.length() - 1;

   while (i >= 0 && j >= 0) {
      if (A.charAt(i) == B.charAt(j)) {
         i--;
         j--;
      } else {
         count++;
         i--;
      }
   }
      return count;
   }

   public static void main(String[] args) {
      String A = "Hello Welcome to Tutorialspoint    ";
      String B = "Tutorialspoint simply easy learning";
      int result = transformString(A, B);
      System.out.println("Minimum number of operations required: " + result);

      A = "EACBD";
      B = "EABCD";
      result = transformString(A, B);
      System.out.println("Minimum number of operations required: " + result);
   }
}

輸出

Minimum number of operations required: 35
Minimum number of operations required: 3

時間和空間複雜度

transform 函式的時間複雜度為 **O(n)**，其中 n 是輸入字串 A 和 B 的長度。這是因為該函式使用兩個指標 i 和 j 從末尾到開頭遍歷字串的字元，以定期比較字元並遞增或遞減指標和計數器。因此，時間複雜度與字串的長度成正比。

transform 函式的空間複雜度為 **O(1)**，這意味著它需要的額外記憶體量與輸入字串的長度無關。該函式不建立任何額外的資料結構或動態分配記憶體；它只需要固定數量的記憶體來儲存變數 count、i 和 j。