当前位置：网站首页>Leetcode subsequence / substring problem

Leetcode subsequence / substring problem

2022-06-22 13:21:00 【Linchong Fengxue mountain temple】

Power button https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-dv83q/

leetcode- Max min problem -v2_MaYingColdPlay The blog of -CSDN Blog 300. Longest ascending subsequence class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ if nums== []: return 0 dp=[1 for _ in range(len(nums))] for i in range(lhttps://blog.csdn.net/MaYingColdPlay/article/details/109143223

Dynamic programming 5 The part ：

1.dp Array meaning

2. The recursive formula

3. initialization

4. traversal order

5. For example, push to dp Array

5. Longest text substring

Dynamic programming

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        max_len=1
        start=0
        dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    if j-i+1==2:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                if dp[i][j]==True:
                    cur_len=j-i+1
                    if cur_len>max_len:
                        max_len=cur_len
                        start=i
        return s[start:start+max_len]

516. The longest palindrome subsequence

Dynamic programming

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]=dp[i+1][j-1]+2
        # Note the order of traversal 
        dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                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]

The longest increasing subsequence

The finger of the sword offer-leetcode- Max min problem - Ideas _MaYingColdPlay The blog of -CSDN Blog https://blog.csdn.net/MaYingColdPlay/article/details/106035602

673. The number of longest increasing subsequences

Dynamic programming

Power button https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/python3-dong-tai-gui-hua-by-caiji-ud-xqam/

class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp=[1 for _ in range(len(nums))]
        cnt=[1 for _ in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    if dp[j]+1>dp[i]:
                        dp[i]=dp[j]+1
                        cnt[i]=cnt[j]
                    elif dp[j]+1==dp[i]:
                        cnt[i]=cnt[i]+cnt[j]
                    else:
                        continue
        res=0
        for i in range(len(nums)):
            if dp[i] == max(dp):
                res+=cnt[i]
        return res

72. Edit distance

Dynamic programming

leetcode- Buying and selling stocks / knapsack problem _MaYingColdPlay The blog of -CSDN Blog 122. The best time to buy and sell stocks II greedy https://blog.csdn.net/MaYingColdPlay/article/details/108184505

Random code recording Identify code Capriccio , Learning algorithms don't get lost https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html#%E6%80%9D%E8%B7%AF

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        # In fact, it is a little similar to the longest common subsequence .
        #dp[i][j] Express word1[:i] and word2[:j] Edit distance between 
        dp=[[0 for i in range(len(word2)+1)] for _ in range(len(word1)+1)]
        # initialization 
        for i in range(len(word2)+1):
            dp[0][i]=i 
        for i in range(len(word1)+1):
            dp[i][0]=i
        # Two layers of circulation 
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #word1 Delete an element 
                    c1=dp[i-1][j]+1
                    #word2 Delete an element 
                    c2=dp[i][j-1]+1
                    # Change an element 
                    c3=dp[i-1][j-1]+1
                    dp[i][j]=min(c1,c2,c3)
        return dp[-1][-1]

583. Deletion of two strings

Ideas ： Same as editing distance , Just one condition is missing . Edit distance is delete , increase , Or change , This title can only be deleted . So put... In the code “ change ” You can just remove the one that is .

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        dp=[[0 for i in range(len(word2)+1)] for _ in range(len(word1)+1)]
        # initialization 
        for i in range(len(word2)+1):
            dp[0][i]=i 
        for i in range(len(word1)+1):
            dp[i][0]=i
        # Two layers of circulation 
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #word1 Delete an element 
                    c1=dp[i-1][j]+1
                    #word2 Delete an element 
                    c2=dp[i][j-1]+1
                    dp[i][j]=min(c1,c2)
        return dp[-1][-1]

115. Different subsequences

Random code recording Identify code Capriccio , Learning algorithms don't get lost https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html#_115-%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97

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

Power button

Longest common subsequence / Substring

The finger of the sword offer-leetcode- Max min problem - Ideas _MaYingColdPlay The blog of -CSDN Blog 1. Double pointer method for the longest substring of non repeating characters , Use one left The pointer , Point to the far left , One cur The pointer , Point to the present , Record the distance between the two . Use a list to record that there are currently no duplicate characters . If there are repeated substrings , Move left The pointer . You don't need two pointers , Use one... Directly list Just judge .list+ From the left pop Out of the existing ....https://blog.csdn.net/MaYingColdPlay/article/details/106035602

940. Different subsequences II

Power button

What is repeated is the previous same element , Previous . Does not include the previous same element .

because , The previous repeating element , This value can be included in the range of new elements , The only repetition of the two is the ones before him .

class Solution(object):
    def distinctSubseqII(self, s):
        """
        :type s: str
        :rtype: int
        """
        maps = collections.defaultdict(int)
        dp = [0 for _ in range(len(s)+1)]
        for i in range(1,len(s)+1):
            dp[i] = dp[i-1]*2 + 1
            if s[i-1] in maps:
                pre = maps[s[i-1]]
                dp[i] = dp[i] - pre - 1
            # What is repeated is the previous same element , Previous . Does not include the previous same element .
            maps[s[i-1]]=dp[i-1]
        return dp[-1] % (10**9+7)

1987. Different number of good subsequences

# Basic ideas and 940 equally .dp[i] Said to i The number of subsequences at the end , Look back before ,dp[i]=2*dp[i-1]-dp[last]
#dp[i]=2*dp[i-1]-dp[last]. With s[i] Number of subsequences at the end , In order to s[i-1] The number of subsequences at the end +s[i-1] The number of subsequences at the end _ Add... To the tail s[i], Plus s[i] In itself 
# Subtract the duplicate ,s[i] The number of subsequences before the last occurrence , Subtract the last occurrence s[i] In itself 
# This question only has 1 and 0, Classification of discussion , Record the last time with 1 The number of subsequences at the end , And last time with 0 The number of subsequences at the end .
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        count1 = 0
        count0 = 0
        if_has0 = 0
        for i in range(len(binary)):
            if binary[i] == "1":
                count1 = count1 + count0 + 1
            if binary[i] == "0":
                count0 = count0 + count1
                if_has0 = 1
        return (count1+count0+if_has0)%(10**9+7)

2262. Total gravity of string

And 940. Different subsequences 2 Think in a similar way , Traverse from left to right , Add the current element at the end of the previous one .

class Solution(object):
    def appealSum(self, s):
        """
        :type s: str
        :rtype: int
        """
        # dp[i] Said to i The substring at the end always attracts 
        dp = [0 for _ in range(len(s)+1)]
        maps = {}
        for i in range(1,len(s)+1):
            #s[i-1] The ending string is i individual 
            dp[i] = dp[i-1] + i
            if s[i-1] in maps:
                last = maps[s[i-1]]
                #s[start:i-1], When start Before the last occurrence of the element , All need to be removed 
                dp[i] = dp[i]  - last
            maps[s[i-1]] = i
        return sum(dp)

828. Count the unique characters in the substring

The same way of thinking 940

Power button

class Solution(object):
    def uniqueLetterString(self, s):
        """
        :type s: str
        :rtype: int
        """
        # With s[i] The unique character of the ending substring , And with s[i-1] The unique character of the ending substring , The relationship between 
        # If s[i] There was no such thing before , With s[i-1] The unique character of the ending substring , All have to be added. 1
        # If s[i] Once before , The last position that appears is j,s[j:i] Add one before 
        # If s[i] There has been a greater than or equal to before 2 Time , The last position that appears is j1,j2,s[j:i] Add one before 
        dp = [0 for _ in range(len(s)+1)]
        maps = collections.defaultdict(list)
        for i in range(1,len(s)+1):
            dp[i] = dp[i-1] + i 
            if s[i-1] in maps:
                last_list = maps[s[i-1]]
                if len(last_list) == 1:
                    dp[i] = dp[i] - 2*last_list[-1]
                else:
                    dp[i] = dp[i] - last_list[-1]-(last_list[-1] - last_list[-2])
            maps[s[i-1]].append(i)
        return sum(dp)