LCS

이번 글에서는 `LCS(Longest Common Subsequence)` 알고리즘에 대해 정리하려고한다. Longest Common Substring도 있지만 이번 글에서는 `Longest Common Subsequence`만 다룰 예정이다. 먼저, `LCS(Longest Common Subsequence)`가 무엇인지 알아보자 What is LCS(Longest Common Subsequence)?`LCS(Longest Common Subsequence)`란 다음과 같다. 두 개의 문자열에서 순서를 유지하면서 일부 문자를 선택해 만들 수 있는 가장 긴 공통 부분 수열  예를 들어, 다음과 같은 문자열이 있다고 가정해보자 String A: ACDBEString B: ABCDE 이 두 문자열의 `LCS`..

난이도: HardProblem Description 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. Problem ExampleExample 1:Input: str1 = "abac", str2 = "cab"Output: "cabac"Explanatio..