[LeetCode] 516. Longest Palindromic Subsequence (golang)

문제

---

Longest Palindromic Subsequence - LeetCode

Given a string s, find the longest palindromic subsequence's length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Example 1: Input: s = "bbbab"Output: 4Explanation: One possible longest palindromic subsequence is "bbbb".

https://leetcode.com/problems/longest-palindromic-subsequence/

• 만들어질 수 있는 가장 긴 대칭 부분수열의 길이 구하기
  • 문자가 몇개 빠질 수도 있음
  • 그래도 순서는 고정

구현

---

• s[start] == s[end] 이면 (start+1 ~ end-1) 에서의 Longest Palindromic Subsequence 길이 + 2

• s[start] != s[end] 이면 Max(LPS(start ~ end-1),LPS(start+1 ~ end))

• 중복제거를 위해 map에 길이 저장

시간 복잡도

• O(N) ~ O(2^N) - 중복제거 ?

• 코드

  var seqMap map[string]int
  
  func longestPalindromeSubseq(s string) int {
      
      seqMap = make(map[string]int)
      bytes := []byte(s)
      return getLength(0,len(s)-1,&bytes)
  }
  
  func getLength(s int, e int, seq *[]byte) int {
      if s>e {
          return 0
      }
      if s==e {
          return 1
      }
      
      str := string((*seq)[s:e+1])
      val, ok := seqMap[str]
      if ok {
          return val
      }
      
      if (*seq)[s] == (*seq)[e] {
          seqMap[str] = getLength(s+1, e-1, seq) + 2
      } else {
          left := getLength(s, e-1, seq)
          right := getLength(s+1, e, seq)
          if left>right {
              seqMap[str] = left
          } else {
              seqMap[str] = right
          }
      }
  
      return seqMap[str]
  }

---

📚

뒤에서부터 2중 for문으로 탐색하는 더 효율적인 방법이 있으며 이 때는 확인할 수 있는 시간복잡도는 O(N^2) 가 된다 ( 기본적인 원리는 같다 )