# 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
}``````

Last updated