AlgorithmAndLeetCode · pull · Jun 12, 2025 · Jun 12, 2025 · Jun 12, 2025 · Jun 12, 2025
diff --git a/...o-Convert-String-with-Operations/3579.Minimum-Steps-to-Convert-String-with-Operations.cpp b/...o-Convert-String-with-Operations/3579.Minimum-Steps-to-Convert-String-with-Operations.cpp
@@ -0,0 +1,46 @@
+class Solution {
+    int count[26][26];
+public:
+    int helper(string& word1, string&word2) {
+        fill(&count[0][0], &count[0][0]+26*26, 0);
+
+        int n = word1.size();
+        for (int k=0; k<n; k++) {
+            if (word1[k]==word2[k]) continue;
+            count[word1[k]-'a'][word2[k]-'a']++;
+        }
+
+        int ans = 0;
+        for (int a=0; a<26; a++)
+            for (int b=0; b<26; b++) {
+                int common = min(count[a][b], count[b][a]);
+                ans+=common;
+                count[a][b]-=common;
+                count[b][a]-=common;
+                ans+=count[a][b];
+            }
+        return ans;
+    }
+
+    int minOperations(string word1, string word2) {
+        int n = word1.size();
+        vector<int>dp(n, INT_MAX/2);
+
+        for (int j=0; j<n; j++)
+            for (int i=0; i<=j; i++) {
+                int ans = INT_MAX/2;
+                string a = word1.substr(i,j-i+1);
+                string b = word2.substr(i,j-i+1);
+                ans = min(ans, helper(a,b));
+
+                string rev = a;
+                reverse(rev.begin(), rev.end());                
+                ans = min(ans, helper(rev,b)+1);
+
+                dp[j] = min(dp[j], (i==0?0:dp[i-1])+ans);
+            }
+
+        return dp[n-1];
+
+    }
+};
diff --git a/Dynamic_Programming/3579.Minimum-Steps-to-Convert-String-with-Operations/Readme.md b/Dynamic_Programming/3579.Minimum-Steps-to-Convert-String-with-Operations/Readme.md
@@ -0,0 +1,7 @@
+### 3579.Minimum-Steps-to-Convert-String-with-Operations
+
+对于区间的问题，我们会思考用区间型的DP是否可行。我们自然会令dp[i]表示针对前i个元素，变换成功所需要的最少操作次数。接下来就是要考虑最后一个区间的位置起点j。因为本题里字符串的长度只有100，我们可以考虑遍历起点j。这样问题就转化为对于区间[j:i]，变化成功所需要的最少操作次数，这样就有`dp[i]=dp[j-1]+helper(j,i)`.
+
+注意到题意中的翻转操作最多只需要一次，我们可以将问题分解成两遍：将word1[j:i]变成Word[j:i]所需要的最少操作数；再将前者翻转一下，同样求变成Word[j:i]所需要的最少操作数。
+
+接下来我们就是设计这样的一个函数，将字符串A怎样高效地只通过swap和replace变成B。贪心是行得通的，因为同一个字符只能用swap或者replace，显然优先使用swap，这样一次操作解决两个地方；等能用的swap都用完了，自然用replace就可以解决剩余的问题。我们用count[a][b]现统计对于字符串A里，字符a需要变成字符b的个数。然后用两个26的循环，遍历所有所有的字符配对{x,y}。显然count[x][y]和count[y][x]可以尽可能地互相抵消，能抵消的就算是swap的操作，剩余不能抵消的部分就是需要的replace的操作。
diff --git a/Readme.md b/Readme.md
@@ -887,6 +887,7 @@
 [2547.Minimum-Cost-to-Split-an-Array](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/2547.Minimum-Cost-to-Split-an-Array) (M)      
 [2911.Minimum-Changes-to-Make-K-Semi-palindromes](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/2911.Minimum-Changes-to-Make-K-Semi-palindromes) (H-)      
 [3077.Maximum-Strength-of-K-Disjoint-Subarrays](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/3077.Maximum-Strength-of-K-Disjoint-Subarrays) (M+)      
+[3579.Minimum-Steps-to-Convert-String-with-Operations](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/3579.Minimum-Steps-to-Convert-String-with-Operations) (H-)      
 * ``区间型 II``   
 [131.Palindrome-Partitioning](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/131.Palindrome-Partitioning) (M+)  
 [312.Burst-Balloons](https://github.com/wisdompeak/LeetCode/tree/master/DFS/312.Burst-Balloons) (H-)