[已解决]Python：【新】每日一题 4

liuzhengyuan

专辑说明 每日废话：最近好忙啊

今天的题目：

给你一个字符串 s，找到 s 中最长的回文子串。
（今天为了回暖，会给超级奖励，暂不定期限）
请按照模板（来自力扣 - leetcode），模板见下

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案

示例 2：

输入：s = "cbbd"
输出："bb"

欢迎大家来答题
模板：

def longestPalindrome(s): # s 为字符串
    <代码内容>
    return s

自己写的参考答案（不要抄袭，不要白嫖）：

游客，如果您要查看本帖隐藏内容请回复

---

来源：力扣（LeetCode）（https://leetcode.cn/problems/longest-palindromic-substring/）

最佳答案

月排行榜 / 总排行榜

ba21

2022-8-11 11:34:41

搞个总结。
爆破：

def longestPalindrome(s):
    if len(s)==1 or s==s[::-1]:
        return s

    res = ''
    for i in range(len(s)+1):
        for j in range(i+2, len(s)+1):
            tmpStr = s[i:j]
            if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
                res = tmpStr
                
    return res if res else s[0]

高效：

def longestPalindrome(s):
    if len(s)==1 or s==s[::-1]:
        return s

    res = ''
    for i in range(1, len(s)+1):
        j = 1
        while (i-j)>=0 and (i+j)<=len(s)+1:
            tmpStr = s[i-j:i+j+1]
            if tmpStr!=tmpStr[::-1]:
                tmpStr = s[i-j:i+j]
                
            if tmpStr!=tmpStr[::-1]:
                break
            if len(tmpStr)>len(res):                
                res = tmpStr                   

            j+=1           

    return res

跳转到最佳答案楼层

柿子饼同学

不知道这样行不行 , 就是求 s 和翻转后的 s 的最长公共子串

def longestPalindrome(s) -> str: # s 为字符串
    
    l = len(s)

    if l == 1: #长度为 1 直接返回
        return s;
    
    rev_s = s[::-1] #翻转一下

    dp = [[0 for _ in range(1000)] for _ in range(1000)]

    pos = 0 #位置
    mxlen = 0 #最长长度

    for i in range(1, l+1):
        for j in range(1, l+1):
            if s[i-1] == rev_s[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > mxlen:
                    mxlen = dp[i][j]
                    pos = i - 1
            else:
                dp[i][j] = 0

    return s[pos - mxlen+1:pos+1]

qq1151985918

def longestPalindrome(s): # s 为字符串
    isPalindrome = lambda x:x == x[::-1]
    allSubSet = lambda x:[x[j:j+i+1] for i in range(len(x)) for j in range(len(x)-i)]
    return sorted(filter(isPalindrome, allSubSet(s)), key=len)[-1]

liuzhengyuan

柿子饼同学 发表于 2022-8-10 07:39
不知道这样行不行 , 就是求 s 和翻转后的 s 的最长公共子串

解答错误

输入：
"aacabdkacaa"
输出：
"aaca"
预期结果：
"aca"

liuzhengyuan

qq1151985918 发表于 2022-8-10 08:36

不好意思，还是按照格式来吧。
不然这样没法测试（要放进一个类作为方法的）

繁宇宙

暴力解法和动态规划都可以嘛

柿子饼同学

liuzhengyuan 发表于 2022-8-10 08:48
解答错误

dolly_yos2

柿子饼同学 发表于 2022-8-10 07:39
不知道这样行不行 , 就是求 s 和翻转后的 s 的最长公共子串

这个方法还是挺让人（让我）眼前一亮的，非常巧妙，只是稍微少了一点细节。
最长公共子串的条件不够充分，还要保证这一组子串来自相同的位置才是原字符串的最长回文子串。在现有基础上稍加修改（给答案更新添加一个额外的判断条件）就可以了。
用 C++ 按照 leetcode 模板写了一个版本，大概是这样的

string longestPalindrome(string s) {
    int length[s.size()][s.size()];
    int result_position = 0;
    int result_length = 0;
    string s_rev(s.crbegin(), s.crend());
    for(int i = 0; i < s.size(); ++i) for(int j = 0; j < s_rev.size(); ++j){
        if(s[i] == s_rev[j]){
            if(i == 0 || j == 0) length[i][j] = 1;
            else length[i][j] = length[i - 1][j - 1] + 1;
            if(length[i][j] > result_length && s.size() + length[i][j] - j - 2 == i){   // 确保子串位置正确
                result_length = length[i][j];
                result_position = i;
            }
        }else{
            length[i][j] = 0;
        }
    }
    return s.substr(result_position - result_length + 1, result_length);
}

除了添加的一个额外判断之外和大佬的代码基本是完全等价的。

qq1151985918

liuzhengyuan 发表于 2022-8-10 08:53
不好意思，还是按照格式来吧。
不然这样没法测试（要放进一个类作为方法的）

def longestPalindrome(s): # s 为字符串
    isPalindrome = lambda x:x == x[::-1]
    allSubSet = lambda x:[x[j:j+i+1] for i in range(len(x)) for j in range(len(x)-i)]
    return sorted(filter(isPalindrome, allSubSet(s)), key=len)[-1]

ba21

def longestPalindrome(s):
    # 获取s中所有子字符串组合
    lst = []
    for i in range(len(s)+1):
        for j in range(i+2, len(s)+1):
            lst.append(s[i:j])
            
    # 按字符串长度大小排序(长->短)
    lst = sorted(lst, key=len, reverse=True)

    # 回文
    for v in lst:
        if v == v[::-1]:
            return v

青出于蓝

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def fun1(var):
            length=len(var)
            i=0
            last=length-1
            b=0
            while (i<length):
                
                if var[i]==var[last]:
                    
                    b+=1
                
                i+=1
                last-=1
            return b
        list1=[]
        for i in range(1,len(s)+1):
            for a in range(len(s)-i+1):
                list1+=[s[a:a+i]]
        list2=[]
        s=""
        for i in list1:
            if fun1(i)==len(i) and len(i)>len(s):
                s=i
        return s  

比较暴力...

柿子饼同学

dolly_yos2 发表于 2022-8-10 11:30
这个方法还是挺让人（让我）眼前一亮的，非常巧妙，只是稍微少了一点细节。
最长公共子串的条件不够充 ...

不敢不敢 , 我之前没想到有这个

ba21

def longestPalindrome(s):
    if len(s)==1 or s==s[::-1]:
        return s

    res = ''
    maxLen = 0
    for i in range(len(s)+1):
        for j in range(i+2, len(s)+1):
            tmpStr = s[i:j]
            if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
                res = tmpStr
    return res

乙方al

一点点儿

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        opp_s = s[::-1]
        s_len = len(s)
        for sub_len in range(1, s_len + 1):
            for sub_start in range(s_len - sub_len + 1):
                
                if opp_s[s_len - sub_start - sub_len:s_len - sub_start] == s[sub_start:sub_start + sub_len]:
                    slongest_start = sub_start
                    longestsub_len = sub_len
                    break
        s = s[slongest_start:slongest_start + longestsub_len]  

        return s

liuzhengyuan

qq1151985918 发表于 2022-8-10 11:40

超出时间限制
输入

"uhrfjotnewtodhmbplsaolnpcdaohiytmfllukijouxipvqohtsgxbtfoxyfkfczkfwhzimbefiohmtimrcxbpgcxogystdkcqujvbxsgirpccdnvejtljftwkdpsqpflzwruwwdzovsbmwbcvlftkjnxqaguvtsycylqzquqkbnybnbaeahbxejhphwrpmymcemuhljwtuvxefqfzjhskuqhifydkxpnfwfxkpeexnjltfqwfvchphmtsrsyayxukvmlqodshqwbeaxhcxdbssnrdzvxtusngwqdxvluauphmmbwmgtazjwvolenegwbmjfwprfuswamyvgrgshqocnhirgyakbkkggviorawadzhjipjjgiwpelwxvtaegauerbwpalofrbghfhnublttqtcmqskcocwwwxpnckrnbepusjyohsrretrqyvgnbezuvwmzizcefxyumtdwnqjkgsktyuacfpnqocqjxcurmipjfqmjqrkdeqsfseyigqlwmzgqhivbqalcxhlzgtsfjbdbfqiedogrqasgmimifdexbjjpfusxsypxobxjtcwxnkpgkdpgskgkvezkriixpxkkattyplnpdbdifforxozfngmlgcunbnubzamgkkfbswuqfqrvzjqmlfqxeqpjaqayodtetsecmfbplscmslpqiyhhykftzkkhshxqvdwmwowokpluwyvavwvofwqtdilwqjgrprukzyhckuspyzaoe"

liuzhengyuan

青出于蓝 发表于 2022-8-10 12:17
比较暴力...

超出时间限制
输入

"civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

liuzhengyuan

ba21 发表于 2022-8-10 13:36

第一个代码：
解答错误：

输入：
"a"
输出：
null
预期结果：
"a"

第二个代码：

输入：
"ac"
输出：
""
预期结果：
"a"

hornwong

看看

ba21

搞个总结。
爆破：

def longestPalindrome(s):
    if len(s)==1 or s==s[::-1]:
        return s

    res = ''
    for i in range(len(s)+1):
        for j in range(i+2, len(s)+1):
            tmpStr = s[i:j]
            if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
                res = tmpStr
                
    return res if res else s[0]

高效：

def longestPalindrome(s):
    if len(s)==1 or s==s[::-1]:
        return s

    res = ''
    for i in range(1, len(s)+1):
        j = 1
        while (i-j)>=0 and (i+j)<=len(s)+1:
            tmpStr = s[i-j:i+j+1]
            if tmpStr!=tmpStr[::-1]:
                tmpStr = s[i-j:i+j]
                
            if tmpStr!=tmpStr[::-1]:
                break
            if len(tmpStr)>len(res):                
                res = tmpStr                   

            j+=1           

    return res