2022-06-14

72. Edit Distance

Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character

• Delete a character

• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500

• word1 and word2 consist of lowercase English letters.

Solution

Approach #0

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for i := 0; i < n+1; i++ {
        dp[0][i] = i
    }

    for i := 1; i < m+1; i++ {
        for j := 1; j < n+1; j++ {
            a, b, c := dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]
            if word1[i-1] != word2[j-1] {
                c += 1
            }
            dp[i][j] = min(a, min(b, c))
        }
    }
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Approach #1

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = i
    }

    var ld int
    for i := 1; i < m+1; i++ {
        ld = dp[0]
        dp[0] = i
        for j := 1; j < n+1; j++ {
            a, b, c := dp[j-1]+1, dp[j]+1, ld
            if word1[i-1] != word2[j-1] {
                c += 1
            }
            ld = dp[j]
            dp[j] = min(a, min(b, c))
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

322. Coin Change

Description

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

• 1 <= coins.length <= 12

• 1 <= coins[i] <= 2^31 - 1

• 0 <= amount <= 10^4

Solution

Approach #0

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i < amount+1; i++ {
        dp[i] = amount + 1
    }
    for i := 1; i <= amount; i++ {
        for _, v := range coins {
            if v <= i {
                dp[i] = min(dp[i], dp[i-v]+1)
            }
        }
    }
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

343. Integer Break

Description

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

• 2 <= n <= 58

Solution

Approach #0

func integerBreak(n int) int {
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        var cur int
        for j := 1; j < i; j++ {
            cur = max(cur, max(j*(i-j), j*dp[i-j]))
        }
        dp[i] = cur
    }
    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

498. Diagonal Traverse

Description

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 10^4

• 1 <= m * n <= 10^4

• -10^5 <= mat[i][j] <= 10^5

Solution

Approach #0

func findDiagonalOrder(mat [][]int) []int {
    m, n := len(mat), len(mat[0])
    ans := make([]int, 0, m*n)
    for i := 0; i < m+n-1; i++ {
        if i%2 == 1 {
            x := max(i-n+1, 0)
            y := min(i, n-1)
            for x < m && y >= 0 {
                ans = append(ans, mat[x][y])
                x++
                y--
            }
        } else {
            x := min(i, m-1)
            y := max(i-m+1, 0)
            for x >= 0 && y < n {
                ans = append(ans, mat[x][y])
                x--
                y++
            }
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}