.Zzumbong

[leetCode/JS] 1143. Longest Common Subsequence ๋ณธ๋ฌธ

coding test/leetCode

[leetCode/JS] 1143. Longest Common Subsequence

์ญ˜๋ด‰ 2022. 12. 15. 10:17

๋‚œ์ด๋„ [ ๐Ÿค” ] 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 and text2 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
๋Œ“๊ธ€์“ฐ๊ธฐ ํผ