Notice
Recent Posts
Recent Comments
Link
.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 |
0 Comments