2025-11-26：字符串轉換需要的最小操作數。用go語言，給定兩個等長字符串 word1 和 word2，要求把 word1 變成 word2。可以先把 word1 分成一個或多個連續片段（子串詳情 - 子串,操作數,數組,Go語言,後端開發福大大架構師每日一題博客

2025-11-26：字符串轉換需要的最小操作數。用go語言，給定兩個等長字符串 word1 和 word2，要求把 word1 變成 word2。

可以先把 word1 分成一個或多個連續片段（子串），然後對這些片段分別進行操作。允許的操作有三種：

在某個片段內，把某個位置上的字符改為另一個小寫字母（替換）。
在片段內交換任意兩個字符的位置（交換）。
將整個片段的字符順序倒過來（反轉）。

每進行一次上述任一操作都計為一次操作。

此外，每個片段中的任意字符下標最多隻能被一次操作所涉及——也就是説，任何字符位置不能被多次用於替換、交換或反轉。

子串指的是原字符串中的連續且非空的一段字符。

目標是用盡可能少的操作次數把 word1 變為 word2，返回所需的最小操作數。

1 <= word1.length == word2.length <= 100。

word1 和 word2 僅由小寫英文字母組成。

輸入： word1 = "abcdf", word2 = "dacbe"。

輸出： 4。

解釋：

將 word1 分割為 "ab"、"c" 和 "df"。操作如下：

對於子串 "ab"：

執行類型 3 的操作："ab" -> "ba"。

執行類型 1 的操作："ba" -> "da"。

對於子串 "c"：無需操作。

對於子串 "df"：

執行類型 1 的操作："df" -> "bf"。

執行類型 1 的操作："bf" -> "be"。

題目來自力扣3579。

分步驟描述

初始化與預處理反轉操作成本（revOp 數組）
- 目的：計算字符串中每個子串通過反轉操作（操作類型3）轉換為目標子串所需的最小操作數。反轉操作允許交換字符位置，其成本取決於字符不匹配的程度。
- 中心擴展法：代碼遍歷所有可能的子串中心（共 2n-1 個，包括字符位置和字符間位置）。對於每個中心點：
  - 設置左右指針 l 和 r，分別向左右擴展，形成子串區間 [l, r]。
  - 在擴展過程中，調用 update 函數處理字符對：
    - 比較 word1[l] 與 word2[r] 以及 word1[r] 與 word2[l]（當 l ≠ r 時），模擬反轉操作下的字符映射。
    - update 函數維護一個字符對計數數組 cnt（大小 26×26）。如果字符對 (x, y) 存在相反方向的配對 (y, x)，則減少操作數（利用交換操作抵消成本）；否則增加操作數。
  - 將當前子串 [l, r] 的反轉操作數記錄到二維數組 revOp[l][r] 中。
- 作用：預處理後，revOp[l][r] 表示子串 word1[l:r+1] 反轉後匹配 word2[l:r+1] 的最小操作數。例如，子串 "ab" 反轉後變為 "ba"，再通過替換操作匹配目標。
動態規劃填充 f 數組
- 目的：計算將 word1 的前綴轉換為 word2 前綴的最小操作數，支持字符串分割為連續片段。每個片段可選擇直接處理或反轉後處理。
- 數組定義：f[i] 表示將 word1 的前 i 個字符轉換為 word2 前 i 個字符的最小操作數（f[0] = 0 表示空前綴）。
- 填充過程：
  - 遍歷每個位置 i（從 0 到 n-1），計算 f[i+1]。
  - 對於每個 i，枚舉所有可能的分割點 j（從 i 遞減到 0），將子串 [j, i] 作為一個片段：
    - 重置 cnt 數組和操作計數器 op。
    - 不反轉情況：順序處理子串 [j, i]，調用 update 函數逐字符比較 word1[k] 和 word2[k]（k 從 j 到 i），計算通過替換和交換操作的成本 op。
    - 反轉情況：直接使用預處理的 revOp[j][i] 作為該片段的反轉操作成本。
    - 取兩種情況的最小值：min(op, revOp[j][i])。
    - 更新 f[i+1] = min(f[i+1], f[j] + min_value)，即前 j 個字符的成本加上當前片段的成本。
- 示例：對於輸入 word1 = "abcdf", word2 = "dacbe"，分割為 "ab"、"c"、"df"：
  - 片段 "ab"：反轉操作成本 revOp[0][1] = 2（先反轉為 "ba"，再替換為 "da"）。
  - 片段 "c"：無需操作（字符匹配）。
  - 片段 "df"：直接操作成本 op = 2（兩次替換）。
  - 總操作數 f[5] = f[2] + 2 + f[3] + 0 + f[5] + 2 = 4。
結果提取
- 動態規劃完成後，f[n] 即為整個字符串轉換的最小操作數。代碼返回 f[n] 作為結果。

時間複雜度和空間複雜度

時間複雜度：
- 預處理 revOp 數組使用中心擴展法，共有 O(n) 箇中心，每個中心擴展最多 O(n) 次，每次擴展調用 O(1) 的 update 函數，因此預處理階段複雜度為 **O(n²)**。
- 動態規劃階段：外層循環遍歷 n 個位置，內層循環對於每個 i 枚舉 j 從 i 到 0，且每個 j 需要處理長度為 O(i-j) 的子串（通過 update 函數）。內層循環的總代價為 O(i²)，因此整體複雜度為 O(n³)（因為 ∑i² 從 0 到 n-1 是 O(n³)）。
- 總時間複雜度：O(n³)，由於 n ≤ 100，實際計算可行。
額外空間複雜度：
- revOp 數組大小為 n × n，佔用 O(n²) 空間。
- 動態規劃數組 f 大小為 n+1，佔用 O(n) 空間。
- 字符對計數數組 cnt 大小為 26×26，為常數空間 **O(1)**。
- 總空間複雜度：O(n²)，主要由 revOp 數組決定。

Go完整代碼如下：

package main

import (
	"fmt"
	"math"
)

func minOperations(s, t string) int {
	var cnt [26][26]int
	var op int
	update := func(x, y byte) {
		if x == y {
			return
		}
		x -= 'a'
		y -= 'a'
		if cnt[y][x] > 0 {
			cnt[y][x]--
		} else {
			cnt[x][y]++
			op++
		}
	}

	n := len(s)
	// 預處理 revOp
	revOp := make([][]int, n)
	for i := range revOp {
		revOp[i] = make([]int, n)
	}
	// 中心擴展法
	// i 為偶數表示奇長度子串，i 為奇數表示偶長度子串
	for i := range 2*n - 1 {
		cnt = [26][26]int{}
		op = 1
		// 從閉區間 [l,r] 開始向左右擴展
		l, r := i/2, (i+1)/2
		for l >= 0 && r < n {
			update(s[l], t[r])
			if l != r {
				update(s[r], t[l])
			}
			revOp[l][r] = op
			l--
			r++
		}
	}

	f := make([]int, n+1)
	for i := range n {
		res := math.MaxInt
		cnt = [26][26]int{}
		op = 0 // 不反轉時的最小操作次數
		for j := i; j >= 0; j-- {
			update(s[j], t[j])
			res = min(res, f[j]+min(op, revOp[j][i]))
		}
		f[i+1] = res
	}
	return f[n]
}

func main() {
	word1 := "abcdf"
	word2 := "dacbe"
	result := minOperations(word1, word2)
	fmt.Println(result)
}

在這裏插入圖片描述

Python完整代碼如下：

# -*-coding:utf-8-*-

def minOperations(s: str, t: str) -> int:
    n = len(s)
    
    # 預處理 revOp
    revOp = [[0] * n for _ in range(n)]
    
    # 中心擴展法
    # i 為偶數表示奇長度子串，i 為奇數表示偶長度子串
    for i in range(2 * n - 1):
        cnt = [[0] * 26 for _ in range(26)]
        op = 1
        
        # 從閉區間 [l,r] 開始向左右擴展
        l = i // 2
        r = (i + 1) // 2
        
        while l >= 0 and r < n:
            # 定義update函數
            def update(x, y):
                nonlocal op
                if x == y:
                    return
                x_idx = ord(x) - ord('a')
                y_idx = ord(y) - ord('a')
                if cnt[y_idx][x_idx] > 0:
                    cnt[y_idx][x_idx] -= 1
                else:
                    cnt[x_idx][y_idx] += 1
                    op += 1
            
            update(s[l], t[r])
            if l != r:
                update(s[r], t[l])
            
            revOp[l][r] = op
            l -= 1
            r += 1
    
    # 動態規劃部分
    f = [0] * (n + 1)
    
    for i in range(n):
        res = float('inf')
        cnt = [[0] * 26 for _ in range(26)]
        op = 0  # 不反轉時的最小操作次數
        
        for j in range(i, -1, -1):
            # 定義update函數
            def update(x, y):
                nonlocal op
                if x == y:
                    return
                x_idx = ord(x) - ord('a')
                y_idx = ord(y) - ord('a')
                if cnt[y_idx][x_idx] > 0:
                    cnt[y_idx][x_idx] -= 1
                else:
                    cnt[x_idx][y_idx] += 1
                    op += 1
            
            update(s[j], t[j])
            res = min(res, f[j] + min(op, revOp[j][i]))
        
        f[i + 1] = res
    
    return f[n]

def main():
    word1 = "abcdf"
    word2 = "dacbe"
    result = minOperations(word1, word2)
    print(result)

if __name__ == "__main__":
    main()

在這裏插入圖片描述

C++完整代碼如下：

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>

using namespace std;

int minOperations(string s, string t) {
    int n = s.length();

    // 預處理 revOp
    vector<vector<int>> revOp(n, vector<int>(n, 0));

    // 中心擴展法
    for (int i = 0; i < 2 * n - 1; i++) {
        vector<vector<int>> cnt(26, vector<int>(26, 0));
        int op = 1;

        // 從閉區間 [l,r] 開始向左右擴展
        int l = i / 2;
        int r = (i + 1) / 2;

        auto update = [&](char x, char y) {
            if (x == y) return;
            int x_idx = x - 'a';
            int y_idx = y - 'a';
            if (cnt[y_idx][x_idx] > 0) {
                cnt[y_idx][x_idx]--;
            } else {
                cnt[x_idx][y_idx]++;
                op++;
            }
        };

        while (l >= 0 && r < n) {
            update(s[l], t[r]);
            if (l != r) {
                update(s[r], t[l]);
            }
            revOp[l][r] = op;
            l--;
            r++;
        }
    }

    // 動態規劃部分
    vector<int> f(n + 1, 0);

    for (int i = 0; i < n; i++) {
        int res = INT_MAX;
        vector<vector<int>> cnt(26, vector<int>(26, 0));
        int op = 0; // 不反轉時的最小操作次數

        auto update = [&](char x, char y) {
            if (x == y) return;
            int x_idx = x - 'a';
            int y_idx = y - 'a';
            if (cnt[y_idx][x_idx] > 0) {
                cnt[y_idx][x_idx]--;
            } else {
                cnt[x_idx][y_idx]++;
                op++;
            }
        };

        for (int j = i; j >= 0; j--) {
            update(s[j], t[j]);
            res = min(res, f[j] + min(op, revOp[j][i]));
        }
        f[i + 1] = res;
    }

    return f[n];
}

int main() {
    string word1 = "abcdf";
    string word2 = "dacbe";
    int result = minOperations(word1, word2);
    cout << result << endl;
    return 0;
}

在這裏插入圖片描述

福大大架構師每日一題博客

福大大架構師每日一題博客

博客 / 詳情