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

liuzhengyuan

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

今天的题目：

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

示例 1：

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

示例 2：

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

欢迎大家来答题
模板：

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

复制代码

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

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

---

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

最佳答案

月排行榜 / 总排行榜

ba21

2022-8-11 11:34:41

搞个总结。
爆破：

1. def longestPalindrome(s):
   
2.     if len(s)==1 or s==s[::-1]:
   
3.         return s
   
4. 
   
5.     res = ''
   
6.     for i in range(len(s)+1):
   
7.         for j in range(i+2, len(s)+1):
   
8.             tmpStr = s[i:j]
   
9.             if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
   
10.                 res = tmpStr
    
11.                
    
12.     return res if res else s[0]
    

复制代码

高效：

1. def longestPalindrome(s):
   
2.     if len(s)==1 or s==s[::-1]:
   
3.         return s
   
4. 
   
5.     res = ''
   
6.     for i in range(1, len(s)+1):
   
7.         j = 1
   
8.         while (i-j)>=0 and (i+j)<=len(s)+1:
   
9.             tmpStr = s[i-j:i+j+1]
   
10.             if tmpStr!=tmpStr[::-1]:
    
11.                 tmpStr = s[i-j:i+j]
    
12.                
    
13.             if tmpStr!=tmpStr[::-1]:
    
14.                 break
    
15.             if len(tmpStr)>len(res):               
    
16.                 res = tmpStr                  
    
17. 
    
18.             j+=1           
    
19. 
    
20.     return res

复制代码

跳转到最佳答案楼层

柿子饼同学

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

1. def longestPalindrome(s) -> str: # s 为字符串
   
2.    
   
3.     l = len(s)
   
4. 
   
5.     if l == 1: #长度为 1 直接返回
   
6.         return s;
   
7.    
   
8.     rev_s = s[::-1] #翻转一下
   
9. 
   
10.     dp = [[0 for _ in range(1000)] for _ in range(1000)]
    
11. 
    
12.     pos = 0 #位置
    
13.     mxlen = 0 #最长长度
    
14. 
    
15.     for i in range(1, l+1):
    
16.         for j in range(1, l+1):
    
17.             if s[i-1] == rev_s[j-1]:
    
18.                 dp[i][j] = dp[i-1][j-1] + 1
    
19.                 if dp[i][j] > mxlen:
    
20.                     mxlen = dp[i][j]
    
21.                     pos = i - 1
    
22.             else:
    
23.                 dp[i][j] = 0
    
24. 
    
25.     return s[pos - mxlen+1:pos+1]

复制代码

qq1151985918

1. def longestPalindrome(s): # s 为字符串
   
2.     isPalindrome = lambda x:x == x[::-1]
   
3.     allSubSet = lambda x:[x[j:j+i+1] for i in range(len(x)) for j in range(len(x)-i)]
   
4.     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 模板写了一个版本，大概是这样的

1. string longestPalindrome(string s) {
   
2.     int length[s.size()][s.size()];
   
3.     int result_position = 0;
   
4.     int result_length = 0;
   
5.     string s_rev(s.crbegin(), s.crend());
   
6.     for(int i = 0; i < s.size(); ++i) for(int j = 0; j < s_rev.size(); ++j){
   
7.         if(s[i] == s_rev[j]){
   
8.             if(i == 0 || j == 0) length[i][j] = 1;
   
9.             else length[i][j] = length[i - 1][j - 1] + 1;
   
10.             if(length[i][j] > result_length && s.size() + length[i][j] - j - 2 == i){   // 确保子串位置正确
    
11.                 result_length = length[i][j];
    
12.                 result_position = i;
    
13.             }
    
14.         }else{
    
15.             length[i][j] = 0;
    
16.         }
    
17.     }
    
18.     return s.substr(result_position - result_length + 1, result_length);
    
19. }

复制代码

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

qq1151985918

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

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

复制代码

ba21

1. def longestPalindrome(s):
   
2.     # 获取s中所有子字符串组合
   
3.     lst = []
   
4.     for i in range(len(s)+1):
   
5.         for j in range(i+2, len(s)+1):
   
6.             lst.append(s[i:j])
   
7.             
   
8.     # 按字符串长度大小排序(长->短)
   
9.     lst = sorted(lst, key=len, reverse=True)
   
10. 
    
11.     # 回文
    
12.     for v in lst:
    
13.         if v == v[::-1]:
    
14.             return v
    

复制代码

青出于蓝

1. class Solution:
   
2.     def longestPalindrome(self, s: str) -> str:
   
3.         def fun1(var):
   
4.             length=len(var)
   
5.             i=0
   
6.             last=length-1
   
7.             b=0
   
8.             while (i<length):
   
9.                
   
10.                 if var[i]==var[last]:
    
11.                     
    
12.                     b+=1
    
13.                
    
14.                 i+=1
    
15.                 last-=1
    
16.             return b
    
17.         list1=[]
    
18.         for i in range(1,len(s)+1):
    
19.             for a in range(len(s)-i+1):
    
20.                 list1+=[s[a:a+i]]
    
21.         list2=[]
    
22.         s=""
    
23.         for i in list1:
    
24.             if fun1(i)==len(i) and len(i)>len(s):
    
25.                 s=i
    
26.         return s  

复制代码

比较暴力...

柿子饼同学

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

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

ba21

1. 
   
2. def longestPalindrome(s):
   
3.     if len(s)==1 or s==s[::-1]:
   
4.         return s
   
5. 
   
6.     res = ''
   
7.     maxLen = 0
   
8.     for i in range(len(s)+1):
   
9.         for j in range(i+2, len(s)+1):
   
10.             tmpStr = s[i:j]
    
11.             if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
    
12.                 res = tmpStr
    
13.     return res
    

复制代码

乙方al

一点点儿

1. class Solution(object):
   
2.     def longestPalindrome(self, s):
   
3.         """
   
4.         :type s: str
   
5.         :rtype: str
   
6.         """
   
7.         opp_s = s[::-1]
   
8.         s_len = len(s)
   
9.         for sub_len in range(1, s_len + 1):
   
10.             for sub_start in range(s_len - sub_len + 1):
    
11.                
    
12.                 if opp_s[s_len - sub_start - sub_len:s_len - sub_start] == s[sub_start:sub_start + sub_len]:
    
13.                     slongest_start = sub_start
    
14.                     longestsub_len = sub_len
    
15.                     break
    
16.         s = s[slongest_start:slongest_start + longestsub_len]  
    
17. 
    
18.         return s

复制代码

liuzhengyuan

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

超出时间限制
输入

1. "uhrfjotnewtodhmbplsaolnpcdaohiytmfllukijouxipvqohtsgxbtfoxyfkfczkfwhzimbefiohmtimrcxbpgcxogystdkcqujvbxsgirpccdnvejtljftwkdpsqpflzwruwwdzovsbmwbcvlftkjnxqaguvtsycylqzquqkbnybnbaeahbxejhphwrpmymcemuhljwtuvxefqfzjhskuqhifydkxpnfwfxkpeexnjltfqwfvchphmtsrsyayxukvmlqodshqwbeaxhcxdbssnrdzvxtusngwqdxvluauphmmbwmgtazjwvolenegwbmjfwprfuswamyvgrgshqocnhirgyakbkkggviorawadzhjipjjgiwpelwxvtaegauerbwpalofrbghfhnublttqtcmqskcocwwwxpnckrnbepusjyohsrretrqyvgnbezuvwmzizcefxyumtdwnqjkgsktyuacfpnqocqjxcurmipjfqmjqrkdeqsfseyigqlwmzgqhivbqalcxhlzgtsfjbdbfqiedogrqasgmimifdexbjjpfusxsypxobxjtcwxnkpgkdpgskgkvezkriixpxkkattyplnpdbdifforxozfngmlgcunbnubzamgkkfbswuqfqrvzjqmlfqxeqpjaqayodtetsecmfbplscmslpqiyhhykftzkkhshxqvdwmwowokpluwyvavwvofwqtdilwqjgrprukzyhckuspyzaoe"

复制代码

liuzhengyuan

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

超出时间限制
输入

1. "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

复制代码

liuzhengyuan

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

第一个代码：
解答错误：

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

第二个代码：

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

hornwong

看看

ba21

搞个总结。
爆破：

1. def longestPalindrome(s):
   
2.     if len(s)==1 or s==s[::-1]:
   
3.         return s
   
4. 
   
5.     res = ''
   
6.     for i in range(len(s)+1):
   
7.         for j in range(i+2, len(s)+1):
   
8.             tmpStr = s[i:j]
   
9.             if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
   
10.                 res = tmpStr
    
11.                
    
12.     return res if res else s[0]
    

复制代码

高效：

1. def longestPalindrome(s):
   
2.     if len(s)==1 or s==s[::-1]:
   
3.         return s
   
4. 
   
5.     res = ''
   
6.     for i in range(1, len(s)+1):
   
7.         j = 1
   
8.         while (i-j)>=0 and (i+j)<=len(s)+1:
   
9.             tmpStr = s[i-j:i+j+1]
   
10.             if tmpStr!=tmpStr[::-1]:
    
11.                 tmpStr = s[i-j:i+j]
    
12.                
    
13.             if tmpStr!=tmpStr[::-1]:
    
14.                 break
    
15.             if len(tmpStr)>len(res):               
    
16.                 res = tmpStr                  
    
17. 
    
18.             j+=1           
    
19. 
    
20.     return res

复制代码