字符串相关

NC55 最长公共前缀

描述

给你一个长度为 $n$ 的字符串数组 $strs$，编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

解法1：纵向扫描

先得到最短的字符串，然后用最短的字符串去一一比较

class Solution:
    def longestCommonPrefix(self , strs ):
        # write code here
        if len(strs) == 0:
            return ""
        strs.sort(key=lambda x:len(x))
        min_len = len(strs[0]) # 得到最短的长度
        temp = strs[0]
        res = ""
        for i in range(1,min_len+1):
            flag = True
            for cur_str in strs:
                if temp[:i] != cur_str[:i]:
                    flag = False
                    break
            if flag == True:
                res = temp[:i]
        return res

NC17 最长回文子串

描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

解法一：动态规划

参考题解：题解 | #最长回文子串#_牛客博客 (nowcoder.net)

定义 dp[i][j] 表示 A[i:j] 是否为回文串。

外循环从后向前遍历，i ->[6 0]

内循环从 i 开始向后遍历，直接结束。

每轮内循环的第一次循环可以解决 单个字符的回文串。

每次循环由外向内检测字串是否为回文串。

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        dp = [
            [0 for _ in range(n)]
            for _ in range(n)
        ] # dp[i][j] 表示 A[i:j] 是否为回文串
        max_len = 0
        # 从右到左
        for i in range(n-1,-1,-1):
            
            # 从左到右
            for j in range(i,n):
                cur_len = j- i +1 # 字串长度
                print(A[i:j+1],i,j,A[i],A[j],cur_len)
                if A[i] == A[j]:
                    # cur_len <= 2那么就为回文串，
                    # cur_len > 2： dp[i][j] = dp[i+1][j-1]
                    if cur_len <= 2:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j]:
                    print(dp[i][j])
                    max_len = max(max_len,cur_len)
        return max_len

NC127 最长公共字串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

解法：暴力解法

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        len1 = len(str1)
        len2 = len(str2)
        if len1 < len2:
            min_len = len1
            min_str = str1
            max_str = str2
        else:
            min_len = len2
            min_str = str2
            max_str = str1
        global_max_str = ""
        for i in range(min_len-1,-1,-1):
            for j in range(i,min_len):
                cur_str = min_str[i:j+1]
                if cur_str in max_str:
                    if len(global_max_str) < len(cur_str):
                        global_max_str = cur_str
                print(str2[i:j+1])
        return global_max_str

解法：动态规划

参考评论区：

【数据结构和算法】动态规划解最长公共子串_牛客博客 (nowcoder.net)

注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。

定义 dp[i][j] 表示字符串 str1中的第 i个字符和 str2中 第 j 个字符为最后一个元素所构成的最长公共字串。

如果要求 dp[i][j]，也就是 str1的第 i 个字符和str2的第j个字符为最后一个元素所构成的最长公共字串，我们首先需要判断这两个字符是否相等。

• 如果不相等，那么他们就不能构成公共字串，也就是

  dp[i][j]=0

• 如果相等，我们还需要计算前面相等字符的个数，其实就是 dp[i-1][j-1]，所有

  dp[i][j]=dp[i-1][j-1]+1

其重点是，以i，j分别是str1，str2的结束字符串，当前的结尾字符记录，会在前一个字符记录上进行迭代，同时在迭代过程中记录字串长度，并记住结束位置

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        maxLength = 0
        maxLastIndex = 0 # 记录最长公共字串最后一个元素在字符串str1中的位置
        len1 = len(str1)
        len2 = len(str2)

        dp = [
            [0 for _ in range(len2+1)]
            for _ in range(len1+1)
        ]

        for i in range(len1):
            for j in range(len2):

                # 递推公式，两个字符相等的情况
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1

                    # 如果遇到了更长的字串，要更新，记录最长字串的长度
                    if dp[i+1][j+1] > maxLength:
                        maxLength = dp[i+1][j+1]
                        maxLastIndex = i
                else:
                    dp[i+1][j+1] = 0 # 递推公式，两个字符不相等的情况
        
        # 对字符串进行截取
        res = str1[maxLastIndex-maxLength+1:maxLastIndex+1]
        return res

解法二：优化

maxLastIndex = 0  # 
maxLength = 0 # 记录最长公共字串的长度
len1 = len(str1)
len2 = len(str2)

dp = [0 for _ in range(len2+1)]

# print("--")
for i in range(0,len1):
    for j in range(len2-1,-1,-1):
      
        if str1[i] == str2[j]:
            # print(
            dp[j+1] = dp[j] + 1
            # print(i,j,dp[j],dp[j+1])
            
            if dp[j+1] > maxLength:
                maxLength = dp[j+1]
                maxLastIndex = i
        else:
            # 如果存在间隔会在这里置为0
            dp[j+1] = 0  # 递推公式，两个字符不相等的情
# print("---")
# print(dp)
res = str1[maxLastIndex-maxLength+1:maxLastIndex+1]
return res