# 2022-06-13

## 1143. Longest Common Subsequence

### Description

Given two strings `text1` and `text2`, return the length of their longest common subsequence. If there is no common subsequence, return `0`.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, `"ace"` is a subsequence of `"abcde"`.

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

``````Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.``````

Example 2:

``````Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.``````

Example 3:

``````Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0. ``````

Constraints:

• `1 <= text1.length, text2.length <= 1000`

• `text1` and `text2` consist of only lowercase English characters.

### Solution

#### Approach #0

``````func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := 0; i < m+1; i++ {
dp[i] = make([]int, n+1)
}
for i, c1 := range text1 {
for j, c2 := range text2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j] + 1
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
}
}
}
return dp[m][n]
}

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

## 583. Delete Operation for Two Strings

### Description

Given two strings `word1` and `word2`, return the minimum number of steps required to make `word1` and `word2` the same.

In one step, you can delete exactly one character in either string.

Example 1:

``````Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".``````

Example 2:

``````Input: word1 = "leetcode", word2 = "etco"
Output: 4``````

Constraints:

• `1 <= word1.length, word2.length <= 500`

• `word1` and `word2` consist of only lowercase English letters.

### Solution

#### Approach #0: Just find the longest common subsequence

``````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)
}
for i, c1 := range word1 {
for j, c2 := range word2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j] + 1
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
}
}
}
return m + n - 2*dp[m][n]
}

func max(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, m+1)
for i := 0; i < m+1; i++ {
dp[i] = make([]int, n+1)
dp[i][0]=i
}
for j:=0;j<n+1;j++ {
dp[0][j]=j
}
for i, c1 := range word1 {
for j, c2 := range word2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j]
} else {
dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j])+1
}
}
}
return dp[m][n]
}

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

## 1051. Height Checker

### Description

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array `expected` where `expected[i]` is the expected height of the `ith` student in line.

You are given an integer array `heights` representing the current order that the students are standing in. Each `heights[i]` is the height of the `ith` student in line (0-indexed).

Return the number of indices where `heights[i] != expected[i]`.

Example 1:

``````Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
heights:  [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.``````

Example 2:

``````Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights:  [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.``````

Example 3:

``````Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights:  [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.``````

Constraints:

• `1 <= heights.length <= 100`

• `1 <= heights[i] <= 100`

### Solution

#### Approach #0

``````func heightChecker(heights []int) (ans int) {
expected := append([]int(nil), heights...)
sort.Ints(expected)
for i, h := range heights {
if h != expected[i] {
ans++
}
}
return
}``````

#### Approach #1

``````func heightChecker(heights []int) (ans int) {
cnt := make([]int, 101)
for _, h := range heights {
cnt[h]++
}
index := 0
for i, c := range cnt {
for ; c > 0; c-- {
if heights[index] != i {
ans++
}
index++
}
}
return
}``````

Last updated