[LeetCode] 1143. Longest Common Subsequence

 轉自LeetCode

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

可以參考 516. Longest Palindromic Subsequence 的想法

在 string 求極值通常可以用 DP 或是 sliding window 來解

按照經驗，通常 subsequence 會用 DP，subarray 會用 sliding window

但非一定，還是得看題目，只是可以當作發想的點

那這題因為是 subsequence，所以先用 DP 來思考

subsequence 的一個特點就是，某個元素可以要或是不要

定義 dp[i][j] 是 text1[i]結尾 和 text2[j] 結尾，這兩個字串最長的 common subsequence

那如果 s[i] = s[j]，dp[i][j] = dp[i-1][j-1] + 1，這個滿直覺的

那當 s[i] != s[j]，可以選擇不要 s[i] 或是不要 s[j]，因此 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

這樣就找到公式了

kotlin

	class Solution {
	fun longestCommonSubsequence(text1: String, text2: String): Int {
	val dp = Array(text1.length+1) { IntArray(text2.length+1) {0}}
	for(i in 1..text1.length) {
	for(j in 1..text2.length) {
	if(text1[i-1] == text2[j-1]) {
	dp[i][j] = dp[i-1][j-1] + 1
	} else {
	dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
	}
	}
	}
	return dp[text1.length][text2.length]
	}
	}

view raw longest_common_subsequence.kt hosted with ❤ by GitHub