Delete Operation for Two Strings Solutions in C++

/// Source : https://leetcode.com/problems/delete-operation-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>

using namespace std;

/// LCS - Memory Search
/// Time Complexity: O(len(word1)*len(word2))
/// Space Complexity: O(len(word1)*len(word2))
class Solution {

private:
    vector<vector<int>> dp;

public:
    int minDistance(string word1, string word2) {

        dp.clear();
        for(int i = 0 ; i < word1.size() ; i ++)
            dp.push_back(vector<int>(word2.size(), -1));
        // cout << "LCS : " << lcs(word1, 0, word2, 0) << endl;
        return word1.size() + word2.size() - 2 * lcs(word1, 0, word2, 0);
    }

private:
    int lcs(const string& word1, int i1, const string& word2, int i2){

        if(i1 == word1.size() || i2 == word2.size())
            return 0;

        if(dp[i1][i2] != -1)
            return dp[i1][i2];

        int res = max(lcs(word1, i1 + 1, word2, i2),
                      lcs(word1, i1, word2, i2 + 1));
        if(word1[i1] == word2[i2])
            res = max(res, 1 + lcs(word1, i1 + 1, word2, i2 + 1));

        return dp[i1][i2] = res;
    }
};

int main() {

    cout << Solution().minDistance("sea", "eat") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/delete-operation-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>

using namespace std;

/// LCS - Dynamic Programming
/// Time Complexity: O(len(word1)*len(word2))
/// Space Complexity: O(len(word1)*len(word2))
class Solution {

public:
    int minDistance(string word1, string word2) {

        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for(int i = 1 ; i <= word1.size() ; i ++)
            for(int j = 1 ; j <= word2.size() ; j ++){
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]);
            }
        return word1.size() + word2.size() - 2 * dp[word1.size()][word2.size()];
    }
};

int main() {

    cout << Solution().minDistance("sea", "eat") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/delete-operation-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>

using namespace std;

/// LCS - Dynamic Programming with Rolling Array
/// Time Complexity: O(len(word1)*len(word2))
/// Space Complexity: O(len(word2))
class Solution {

public:
    int minDistance(string word1, string word2) {

        vector<vector<int>> dp(2, vector<int>(word2.size() + 1, 0));
        for(int i = 1 ; i <= word1.size() ; i ++)
            for(int j = 1 ; j <= word2.size() ; j ++){
                dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1]);
                if(word1[i-1] == word2[j-1])
                    dp[i%2][j] = max(dp[i%2][j], 1 + dp[(i-1)%2][j-1]);
            }
        return word1.size() + word2.size() - 2 * dp[word1.size()%2][word2.size()];
    }
};

int main() {

    cout << Solution().minDistance("sea", "eat") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/delete-operation-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>

using namespace std;

/// Memory Search
/// Directly solve the minimum deleted character number problem
///
/// Time Complexity: O(len(word1)*len(word2))
/// Space Complexity: O(len(word2))
class Solution {

private:
    vector<vector<int>> dp;

public:
    int minDistance(string word1, string word2) {

        dp.clear();
        for(int i = 0 ; i < word1.size() ; i ++)
            dp.push_back(vector<int>(word2.size(), -1));

        return minDistance(word1, word1.size() - 1, word2, word2.size() - 1);
    }

private:
    int minDistance(const string& word1, int i1, const string& word2, int i2){

        if(i1 < 0)
            return i2 + 1;

        if(i2 < 0)
            return i1 + 1;

        if(dp[i1][i2] != -1)
            return dp[i1][i2];

        int res = min(1 + minDistance(word1, i1 - 1, word2, i2),
                      1 + minDistance(word1, i1, word2, i2 - 1));
        if(word1[i1] == word2[i2])
            res = min(res, minDistance(word1, i1 - 1, word2, i2 - 1));

        return dp[i1][i2] = res;
    }
};

int main() {

    cout << Solution().minDistance("sea", "eat") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/delete-operation-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Directly solve the minimum deleted character number problem
///
/// Time Complexity: O(len(word1)*len(word2))
/// Space Complexity: O(len(word1)*len(word2))
class Solution {

public:
    int minDistance(string word1, string word2) {

        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for(int i = 0 ; i <= word1.size() ; i ++)
            dp[i][0] = i;
        for(int j = 0 ; j <= word2.size() ; j ++)
            dp[0][j] = j;

        for(int i = 1 ; i <= word1.size() ; i ++)
            for(int j = 1 ; j <= word2.size() ; j ++){
                dp[i][j] = min(1 + dp[i-1][j], 1 + dp[i][j-1]);
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
            }
        return dp[word1.size()][word2.size()];
    }
};

int main() {

    cout << Solution().minDistance("sea", "eat") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/delete-operation-for-two-strings/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming with 1-D Rolling Array
/// Directly solve the minimum deleted character number problem
///
/// Time Complexity: O(len(word1)*len(word2))
/// Space Complexity: O(len(word2))
class Solution {

public:
    int minDistance(string word1, string word2) {

        vector<vector<int>> dp(2, vector<int>(word2.size() + 1, 0));
        for(int j = 0 ; j <= word2.size() ; j ++)
            dp[0][j] = j;

        for(int i = 1 ; i <= word1.size() ; i ++){
            dp[i%2][0] = i;
            for(int j = 1 ; j <= word2.size() ; j ++){
                dp[i%2][j] = min(1 + dp[(i-1)%2][j], 1 + dp[i%2][j-1]);
                if(word1[i-1] == word2[j-1])
                    dp[i%2][j] = min(dp[i%2][j], dp[(i-1)%2][j-1]);
            }
        }
        return dp[word1.size()%2][word2.size()];
    }
};

int main() {

    cout << Solution().minDistance("sea", "eat") << endl;

    return 0;
}