Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 잠실새내
- 나쫌
- 3d퍼즐
- 맛집
- 메탈퍼즐
- 코테
- 미앤아이
- 누룽지소금빵
- 코딩테스트
- 메일우유
- 토이프로젝트
- 송리단
- 밥먹고
- 서울제빵소
- javascript
- 노노그램
- 하스스톤
- 천등
- DIY
- 뜨아거
- 취미
- 버즈2프로
- 발더스게이트
- LeetCode
- 발더스3
- 알고리즘테스트
- 바질토마토뭐시기
- 눈알빠지겠네
- 발더스모드
- 게임
Archives
- Today
- Total
.Zzumbong
[leetCode/JS] 1143. Longest Common Subsequence 본문
난이도 [ 🤔 ] Medium
문제 설명
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
andtext2
consist of only lowercase English characters.
내 솔루션
- 처음에 단순 반복으로 풀다가. 예외적인 상황이 많아서 DP로 풀어야한다는 것까지 생각했지만
- 점화식이나 아이디어가 떠올르지 않아서 구글링함..ㅠ_ㅠ
- 자세한 설명은 여기서 https://sumim.tistory.com/entry/LeetCode-1143-Longest-Common-Subsequence 구경하세요
var longestCommonSubsequence = function(text1, text2) {
let matrix = Array(text1.length + 1).fill(0).map(x => Array(text2.length + 1).fill(0))
for(let i = 1; i < matrix.length; i++){
for(let j = 1; j < matrix[0].length; j++){
if(text1[i-1] === text2[j-1]){
matrix[i][j] = matrix[i-1][j-1] + 1;
} else {
matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1]);
}
}
}
return matrix[text1.length][text2.length];
};
감상평
- DP는 개념이긴한데, 2차원 배열을 만들어서 이전과 비교하는 방식은 처음이네!
- 어려운 문제는 참 많구만 어렵다 어려워
- 빠르긴 겁나 빠르네.
'coding test > leetCode' 카테고리의 다른 글
[leetCode/JS] 150. Evaluate Reverse Polish Notation (0) | 2022.12.17 |
---|---|
[leetCode/JS] 232. Implement Queue using Stacks (0) | 2022.12.16 |
[leetCode/JS] 152. Maximum Product Subarray (0) | 2022.12.14 |
[leetCode/JS] 198. House Robber (0) | 2022.12.14 |
[leetCode/JS] 931. Minimum Falling Path Sum (0) | 2022.12.13 |
Comments