Leetcode daily solutions

Delete Operation for Two Strings.cpp

// Leetcode daily challenge - 14.06.22
// https://leetcode.com/problems/delete-operation-for-two-strings
// Top Down DP approach - O(n*m) space and O(n^2) time complexity

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(),m = word2.size();
        int dp[n+1][m+1];
       
        memset(dp , 0 , sizeof(dp));
       
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(word1[i-1] == word2[j-1]) {
                    dp[i][j] = 1+dp[i-1][j-1];
                } else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        
        return n+m-(dp[n][m]<<1);
    }
};

Triangle.cpp

// Leetcode daily challenge - 13.06.22
// https://leetcode.com/problems/triangle
// Bottom up DP approach - O(1) space and O(n^2) time complexity

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i=triangle.size()-2;i>=0;i--) {
            for(int j=0;j<=i;j++) {
               triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};