[LeetCode] 1092. Shortest Common Supersequence

轉自LeetCode

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

 

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

 

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

Solution

1143. Longest Common Subsequence 的衍生題

如果能找到 LCS，最後只要將沒有出現在 LCS 的字元串起來，就能找到答案

將 DP 改存 string，也就是 LCS 的值，而不是長度

這題覺得最難的地方是組答案的地方

首先，要記得一個觀念，subsequence 也是有順序的

s1 = aaab 和 s2 = aadb 的 LCS 是 aab

不論在s1和s2，一定是會先出現兩個a，才會出現b

因此，最後組答案的時候，可以用歷遍 LCS 的方式

如果和當下LCS字元不同的值的時候，就放到最後答案裡

如果和當下LCS字元相同的時候，就單純移動指標

當然，LCS 本身的字元也都要放到答案裡

最後，檢查一下 s1 和 s2 在指標後面還有沒有字串，有的話就全部加進來就好

kotlin

	class Solution {
	fun shortestCommonSupersequence(str1: String, str2: String): String {
	val dp = Array(str1.length+1) { Array<String>(str2.length+1) {""} }
	for(i in 1..str1.length) {
	for(j in 1..str2.length) {
	if(str1[i-1] == str2[j-1]) {
	dp[i][j] = dp[i-1][j-1] + str1[i-1]
	} else {
	dp[i][j] = if(dp[i-1][j].length > dp[i][j-1].length) {
	dp[i-1][j]
	} else {
	dp[i][j-1]
	}
	}
	}
	}
	val lcs = dp.last().last()
	var sb = StringBuilder()
	var index1 = 0
	var index2 = 0
	for(c in lcs) {
	while(index1 < str1.length && str1[index1] != c) {
	sb.append(str1[index1++])
	}
	while(index2 < str2.length && str2[index2] != c) {
	sb.append(str2[index2++])
	}
	sb.append(c)
	++index1
	++index2
	}
	return sb.append(str1.substring(index1)).append(str2.substring(index2)).toString()
	}
	}

view raw shortest_common_supersequence.kt hosted with ❤ by GitHub