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
- ์ก๋ฆฌ๋จ
- ์ฝํ
- ํ์ค์คํค
- ์กํ
- ์ ํฌ๋ธ
- ์ฝ๋ฉํ ์คํธ
- ์ ์ฅ
- ์๊ณ ๋ฆฌ์ฆ
- javascript
- LeetCode
- ๊ฒ์
- ์ ์ค
- ์ฐ์ฃผ
- ์ ์ค์๋ด
- ๋์ซ
- Sort
- ๋ง์ง
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