57 lines
1.5 KiB
Kotlin
57 lines
1.5 KiB
Kotlin
class Solution {
|
|
fun shortestCommonSupersequence(
|
|
str1: String,
|
|
str2: String,
|
|
): String {
|
|
val (n, m) = str1.length to str2.length
|
|
val dp = Array(n + 1) { IntArray(m + 1) }
|
|
|
|
// Initialize base cases
|
|
(0..n).forEach { y -> dp[y][0] = y }
|
|
(0..m).forEach { x -> dp[0][x] = x }
|
|
|
|
// Precompute
|
|
(1..n).flatMap { y ->
|
|
(1..m).map { x -> x to y }
|
|
}.forEach { (x, y) ->
|
|
dp[y][x] =
|
|
when {
|
|
str1[y - 1] == str2[x - 1] -> dp[y - 1][x - 1] + 1
|
|
else -> 1 + listOf(dp[y - 1][x], dp[y][x - 1]).min()!!
|
|
}
|
|
}
|
|
|
|
val supersequence = StringBuilder()
|
|
var (x, y) = m to n
|
|
|
|
while (y > 0 && x > 0) {
|
|
when {
|
|
str1[y - 1] == str2[x - 1] -> {
|
|
supersequence.append(str1[y - 1])
|
|
y--
|
|
x--
|
|
}
|
|
dp[y - 1][x] < dp[y][x - 1] -> {
|
|
supersequence.append(str1[y - 1])
|
|
y--
|
|
}
|
|
else -> {
|
|
supersequence.append(str2[x - 1])
|
|
x--
|
|
}
|
|
}
|
|
}
|
|
|
|
while (y > 0) {
|
|
supersequence.append(str1[y - 1])
|
|
y--
|
|
}
|
|
|
|
while (x > 0) {
|
|
supersequence.append(str2[x - 1])
|
|
x--
|
|
}
|
|
|
|
return supersequence.reverse().toString()
|
|
}
|
|
}
|