Why is the answer to Test Case #2 0? I don’t see a way in which there could be 0 cost for that one.
func deleteString(costs []int, s1 string, s2 string) int {
dp := make([][]int, len(s1)+1); for r := range dp { dp[r] = make([]int, len(s2)+1) }
for r := 1; r <= len(s1); r++ { dp[r][0] = dp[r-1][0] + costs[s1[r-1]-'a'] }
for c := 1; c <= len(s2); c++ { dp[0][c] = dp[0][c-1] + costs[s2[c-1]-'a'] }
for r := 1; r <= len(s1); r++ {
for c := 1; c <= len(s2); c++ {
if s1[r-1] == s2[c-1] {
dp[r][c] = dp[r-1][c-1]
} else {
dp[r][c] = Min(costs[s1[r-1]-'a']+dp[r-1][c], costs[s2[c-1]-'a']+dp[r][c-1])
}
}
}
return dp[len(s1)][len(s2)]
}
func Min(a, b int) int {
if a < b { return a }
return b
}
If you have a quick glance at the input, since the last value is 1 for the costs, you think it’s the cost for ‘z’, but actually it’s not … The array length is more than 26 so the value for ‘z’ is zero, which is how you get a zero result here.
Why do we do len of 1001?
Not able to type-in code for this problem in editor but for others editor is working fine. I have tried refreshing the tab and restarting the browser.
@admin please look into this.
Top down approach
using namespace std;
int dfs(vector<int> & costs, string & s1, string & s2, int m, int n, vector<vector<int>> & dp) {
if(m < 0 && n < 0) return 0;
if(m < 0 && n >= 0){
int total = 0;
while(n >=0 ) {
total += costs[s2[n--] - 'a'];
}
return total;
}
if(n < 0 && m >= 0) {
int total = 0;
while(m >= 0) {
total += costs[s1[m--] - 'a'];
}
return total;
}
if(dp[m][n]) return dp[m][n];
int s1cost = costs[s1[m] - 'a'];
int s2cost = costs[s2[n] - 'a'];
// cout << m << " " << n << endl;
// cout << s1cost << ":" << s2cost << endl;
int minCost = 0;
if(s1[m] != s2[n]) {
minCost = min(s1cost + dfs(costs, s1, s2, m-1, n, dp), s2cost + dfs(costs, s1, s2, m, n-1, dp));
}else{
minCost = dfs(costs, s1, s2, m-1, n-1, dp);
}
//cout << m << " " << n << " : " << minCost << endl;
return dp[m][n] = minCost;
}
int delete_string(std::vector<int> costs, std::string s1, std::string s2) {
// WRITE YOUR BRILLIANT CODE HERE
int m = s1.size();
int n = s2.size();
int k = max(m, n);
vector<vector<int>> dp(k, vector<int>(k, 0));
return dfs(costs, s1, s2, m-1, n-1, dp);
}
I understand it is nice to be able to progressively be able to get to the tabular solution. But most of the time reasoning through recursive and recursive through memoization first helps make that transition easier.
It would be nice if they could include the recursive and recursive + memo examples as well
// Here is naive recursive
function deleteString(costs, s1, s2) {
return helper(costs, s1, s2, 0, 0);
}
const helper = (costs, s1, s2, p1, p2) => {
// base cases
// both pointers out of bounds
if(p1 >= s1.length && p2 >= s2.length) return 0
// both letters are the same
if(s1.charAt(p1) === s2.charAt(p2)) return helper(costs, s1, s2, p1 + 1, p2 + 1)
// p1 out of bounds, delete s2
if(p1 >= s1.length) return getCost(s2, p2, costs) + helper(costs, s1, s2, p1, p2 + 1);
// p2 out of bounds, delete s1
if(p2 >= s2.length) return getCost(s1, p1, costs) + helper(costs, s1, s2, p1 + 1, p2);
// chose to delete s1 or s2
const cost1 = getCost(s1, p1, costs) + helper(costs, s1, s2, p1 + 1, p2);
const cost2 = getCost(s2, p2, costs) + helper(costs, s1, s2, p1, p2 + 1);
return Math.min(cost1, cost2);
}
const getCost = (str, ptr, costs) => {
const letter = str.charAt(ptr);
const idx = letter.charCodeAt(0) - ‘a’.charCodeAt(0);
return costs[idx];
}
Javascript top-down memoized
function deleteString(costs, s1, s2) {
const memo = new Array(s1.length + 1)
.fill(Number.MAX_SAFE_INTEGER)
.map(e => new Array(s2.length + 1).fill(Number.MAX_SAFE_INTEGER))
return helper(costs, s1, s2, 0, 0, memo);
}
const helper = (costs, s1, s2, p1, p2, memo) => {
// base cases
// both pointers out of bounds
if(p1 >= s1.length && p2 >= s2.length) return 0
if(memo[p1][p2] < Number.MAX_SAFE_INTEGER) return memo[p1][p2];
// both letters are the same
if(s1.charAt(p1) === s2.charAt(p2)) {
memo[p1][p2] = helper(costs, s1, s2, p1 + 1, p2 + 1, memo)
} else if(p1 >= s1.length) {
// p1 out of bounds, delete s2
memo[p1][p2] = getCost(s2, p2, costs) + helper(costs, s1, s2, p1, p2 + 1, memo);
} else if(p2 >= s2.length) {
// p2 out of bounds, delete s1
memo[p1][p2] = getCost(s1, p1, costs) + helper(costs, s1, s2, p1 + 1, p2, memo);
} else {
// chose to delete s1 or s2
const cost1 = getCost(s1, p1, costs) + helper(costs, s1, s2, p1 + 1, p2, memo);
const cost2 = getCost(s2, p2, costs) + helper(costs, s1, s2, p1, p2 + 1, memo);
memo[p1][p2] = Math.min(cost1, cost2);
}
return memo[p1][p2]
}
const getCost = (str, ptr, costs) => {
const letter = str.charAt(ptr);
const idx = letter.charCodeAt(0) - 'a'.charCodeAt(0);
return costs[idx];
}
Top-down approach, similar to Edit Distance
def delete_string(costs: List[int], s1: str, s2: str) -> int:
min_dist = inf
@lru_cache(None)
def dp(i, j, dist):
nonlocal min_dist
if i == len(s1) and j == len(s2):
min_dist = min(min_dist, dist)
return
if i == len(s1):
for l in range(j, len(s2)):
letter = s2[l]
ord_letter = ord(letter)-97
dist += costs[ord_letter]
min_dist = min(min_dist, dist)
return
if j == len(s2):
for l in range(i, len(s1)):
letter = s1[l]
ord_letter = ord(letter)-97
dist += costs[ord_letter]
min_dist = min(min_dist, dist)
return
if s1[i] == s2[j]:
dp(i+1, j+1, dist)
else:
dp(i+1, j, dist+costs[ord(s1[i])-97])
dp(i, j+1, dist+costs[ord(s2[j])-97])
dp(0,0,0)
return min_dist