// given two strings s1 and s2 (|s1| == |s2|) make s1 same as s2 using following 2 operations // 1. swap any two elements at indices i and j in s1 with cost x , // 2. swap two adjacent elements with cost 1 // achieve this with minimum cost #define pb push_back class Solution { public: vector<double> dp; double findMin(vector<int>& diff, int i, int x){ if( i == 0) return x / 2.0; if( i == -1) return 0; if(dp[i] != -1) return dp[i]; double left = findMin(diff, i-1, x) + x/2.0; double right = findMin(diff, i-2 , x) + diff[i] - diff[i-1]; return dp[i] = min(left, right); } int minOperations(string s1, string s2, int x) { vector<int> diffs; int n = s1.length(); for(int i = 0; i < n; i++) if(s1[i] != s2[i]) diffs.pb(i); if(diffs.size() & 1) return -1; dp.resize(diffs.size(),-1); return (int)findMin(diffs, diffs.size() - 1, x); } }; // Its O(n) time and O(n) space;
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter