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