leetcode 647(팰린드롬), 516(팰린드롬), 1143(팰린드롬, lcs), 583

647 https://leetcode.com/problems/palindromic-substrings/

 

이전에 https://qkqhxla1.tistory.com/1059 에서 leetcode 5번 문제에 대한 풀이를 적었었는데 같은 문제다.

class Solution:
    def countSubstrings(self, s: str) -> int:
        ret = 0
        for i in range(len(s)):
            l,r = i, i
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                ret += 1
                l -= 1
                r += 1
            
            l,r = i, i+1
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                ret += 1
                l -= 1
                r += 1
        return ret

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

 

이것도 이전에 https://qkqhxla1.tistory.com/780여기서 풀었던거랑 비슷하다.
iterative

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0]*len(s) for i in range(len(s))]
        for i in range(len(s)-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, len(dp)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][-1]

recursive

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dps = [[0]*len(s) for i in range(len(s))]
        def dp(l, r):
            if dps[l][r] != 0:
                return dps[l][r]
            elif l == r:
                return 1
            elif l > r:
                return 0
            
            if s[l] == s[r]:
                dps[l][r] = dp(l+1, r-1) + 2
            else:
                dps[l+1][r] = dp(l+1, r)
                dps[l][r-1] = dp(l, r-1)
                dps[l][r] = max(dps[l+1][r], dps[l][r-1])
            return dps[l][r]
        return dp(0, len(s)-1)

1143 https://leetcode.com/problems/longest-common-subsequence/

 

일반적인 dp문제중 하나다.

class Solution(object):
    def longestCommonSubsequence(self, t1, t2):
        dp = [[0]*(len(t2)+1) for i in range(len(t1)+1)]
        for i in range(len(t1)):
            for j in range(len(t2)):
                if t1[i] == t2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        return dp[-1][-1]

583 https://leetcode.com/problems/delete-operation-for-two-strings/

 

바로 위의 longest common subsequence를 구한다. 그리고 첫번째, 두번째 단어에서 common subsequence길이만큼의 차이가 답이다.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0]*(len(word2)+1) for i in range(len(word1)+1)]
        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i] == word2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        return len(word1) - dp[-1][-1] + len(word2) - dp[-1][-1]