Blog | Autzoko Lang

Given two string word1 and word2, return the minimum number of operation required to converted word1 to word2.

Following three operations are permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example:

1
2

Input: word1 = "horse", word2 = "ros";
Output: 3;

Constraints:

• 0 <= len(word1), len(word2) <= 500
• word1 and word2 consist of lower case English letters

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class EditDistance {
public:
    int minDistance(string word1, string word2) {
        word1 = " " + word1;
        word2 = " " + word2;

        int **matrix = new int*[word1.size()];
        for(int i = 0; i < word1.size(); i++) {
            matrix[i] = new int[word2.size()];
            fill_n(matrix[i], word2.size(), 0);
        }

        for(int i = 0; i < word1.size(); i++) {
            for(int j = 0; j < word2.size(); j++) {
                if(_min_(i, j) == 0) matrix[i][j] = _max_(i, j);
                else {
                    if(word1[i] == word2[j]) {
                        matrix[i][j] = matrix[i - 1][j - 1];
                    } else {
                        matrix[i][j] = _trimin_(
                            matrix[i - 1][j - 1],
                            matrix[i][j - 1],
                            matrix[i - 1][j]
                        ) + 1;
                    }
                }
            }
        }
        return matrix[word1.size() - 1][word2.size() - 1];
    }

private:
    int _min_(int i, int j) {
        return i < j ? i : j;
    }
    int _max_(int i, int j) {
        return i > j ? i : j;
    }
    int _trimin_(int x, int y, int z) {
        return _min_(x, y) < _min_(y, z) ? _min_(x, y) : _min_(y, z);
    }
};

Explanation:

Use matrix[i][j] to represents the edit distance between string word1[0…i] and word2[0…j]. The index of string’s content begins at 1, matrix[0][0] indicates the case that word1 and word2 are both vacant, which means their edit distance is 0. So, it is obvious that matrix[0][j] is the case when word1 is empty and the length of word2 is j, and their edit distance should be just j. Similarly, matrix[0][i] is the case when the length of word1 is i and word2 is empty, their edit distance is i.

Then we can deduce the equation for the above three operations accordingly:

• matrix[i - 1][j] + 1: insert the last character of word1 into the tail of word2
• matrix[i][j - 1] + 1: delete the last character of word2
• matrix[i - 1][j - 1] + 1: replace the last character of word2 by the last character of word1

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example:

1
2

Input: n = 3;
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Constraints:

• 1 <= n <= 8

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class GenerateParentheses {
public:
    vector<string> res;
    vector<string> generateParentheses(int n) {
        if(n <= 0) return res;
        p("", n, n);
        return res;
    }

    void p(string str, int left, int right) {
        if(left == 0 && right == 0) {
            res.push_back(str);
            return;
        }
        if(left == right) {
            p(str + "(", left - 1, right);
        } else {
            if(left > 0) {
                p(str + "(", left - 1, right);
            }
            p(str + ")", left, right - 1);
        }
    }
};

Explanation:

The number of remained left parenthese must be less or equal to the number of remained right parenthese. If the number of remained left parenthese equals to the remained right one, the next can only be a left parenthese. If the number of remained left parenthese is less than the right one, the next one can be either a left parenthese or a right parenthese. This problem can be solved by using recursion algorithm.

Given a m * n grid filled with non-negative numbers, find a path from top left to bottom right, which minizes the sum of all numbers along its path.

• Moves can only be taken down or right at any point in time.

Example:

1
2

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]];
Output: 7;

Constraints:

• 1 <= m, n <= 200
• 0 <= grid[i, j] <= 200

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class MinimumPathSum {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n_row = grid.size();
        int n_col = grid[0].size();
        int **dp = new int*[n_row];
        for(int i = 0; i < n_row; i++) {
            dp[i] = new int[n_col];
            fill_n(dp[i], n_col, INT_MAX);
        }
        dp[0][0] = grid[0][0];

        for(int i = 0; i < n_row; i++) {
            for(int j = 0; j < n_col; j++) {
                if(i) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j] < dp[i][j] ? dp[i - 1][j] + grid[i][j] : dp[i][j];
                }
                if(j) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j] < dp[i][j] ? dp[i][j - 1] + grid[i][j] : dp[i][j];
                }
            }
        }
        return dp[n_row - 1][n_col - 1];
    }
};

Explanation:

Using a dp array to indicate the current minimum path sum. And this sum can only be the sum of the up dp point and current grid point or the left dp point and current grid point. The dp function can be defined as follow:

1

dp[i, j] := min(dp[i - 1, j] + grid[i, j], dp[i, j - 1] + grid[i, j])

Welcome to my personal blog. I open this blog when I am about to graduate from my university, at the time I extremely want to use something to document my life and things I’ve learned. And now I’m on my way to the United States to start a brand new experience of studying. I want to keep some memories through this blog, and meanwhile take some notes about the things that might be useful to my future development.

About This Blog

Due to my major is computer science/engineering, so most of study notes are related to fields like computer science, computer engineering, software developing, etc., I have to admit that I’m not excel at such subjects, but I am still keen on them and wish to make something big from my own hands. Hope this blog can witness my improvements :)

This blog does not only focus on such academic matters. For other parts, I will upload some of my daily life records, like photos, music, and maybe some unexpected inspiration and ideas. And I will write each blog article in English as possible as I can, to improve my English writing skills, and maybe it’s benefit to my future experience in the US🙂

Hope you enjoy my blog, and discover something new!

Crescat Scientia Vita Excolatur

益智厚生