论坛 › Python交流 › Python：【新】每日一题 4

liuzhengyuan 发表于 2022-8-10 02:33:00

Python：【新】每日一题 4

本帖最后由 liuzhengyuan 于 2022-8-10 03:55 编辑

专辑说明 每日废话：最近好忙啊{:10_269:}

今天的题目：

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

示例 1：

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

输入：s = "cbbd"
输出："bb"
欢迎大家来答题{:10_298:}
模板：def longestPalindrome(s): # s 为字符串
    <代码内容>
    return s

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

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

柿子饼同学 发表于 2022-8-10 07:39:05

本帖最后由 柿子饼同学 于 2022-8-10 07:40 编辑

不知道这样行不行 , 就是求 s 和翻转后的 s 的最长公共子串{:10_266:}
def longestPalindrome(s) -> str: # s 为字符串
   
    l = len(s)

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

    dp = [ for _ in range(1000)]

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

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

    return s

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

本帖最后由 qq1151985918 于 2022-8-10 11:55 编辑

def longestPalindrome(s): # s 为字符串
    isPalindrome = lambda x:x == x[::-1]
    allSubSet = lambda x: 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 08:48:41

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

解答错误
输入：
"aacabdkacaa"
输出：
"aaca"
预期结果：
"aca"

liuzhengyuan 发表于 2022-8-10 08:53:59

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


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

繁宇宙 发表于 2022-8-10 09:14:48

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

柿子饼同学 发表于 2022-8-10 10:32:20

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

{:10_266:}

dolly_yos2 发表于 2022-8-10 11:30:06

本帖最后由 dolly_yos2 于 2022-8-10 11:31 编辑

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

这个方法还是挺让人（让我）眼前一亮的，非常巧妙，只是稍微少了一点细节。
最长公共子串的条件不够充分，还要保证这一组子串来自相同的位置才是原字符串的最长回文子串。在现有基础上稍加修改（给答案更新添加一个额外的判断条件）就可以了。
用 C++ 按照 leetcode 模板写了一个版本，大概是这样的
string longestPalindrome(string s) {
    int length;
    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 == s_rev){
            if(i == 0 || j == 0) length = 1;
            else length = length + 1;
            if(length > result_length && s.size() + length - j - 2 == i){   // 确保子串位置正确
                result_length = length;
                result_position = i;
            }
      }else{
            length = 0;
      }
    }
    return s.substr(result_position - result_length + 1, result_length);
}
除了添加的一个额外判断之外和大佬的代码基本是完全等价的。

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

本帖最后由 qq1151985918 于 2022-8-10 11:55 编辑

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

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

ba21 发表于 2022-8-10 12:16:42

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

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

青出于蓝 发表于 2022-8-10 12:17:13

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==var:
                  
                  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+=]
      list2=[]
      s=""
      for i in list1:
            if fun1(i)==len(i) and len(i)>len(s):
                s=i
      return s
比较暴力...

柿子饼同学 发表于 2022-8-10 13:01:56

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

不敢不敢 , 我之前没想到有这个{:10_266:}

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

本帖最后由 ba21 于 2022-8-10 19:09 编辑


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
            if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
                res = tmpStr
    return res

乙方al 发表于 2022-8-10 14:59:14

本帖最后由 乙方al 于 2022-8-10 15:06 编辑

{:10_243:}

一点点儿 发表于 2022-8-10 20:16:35

本帖最后由 一点点儿 于 2022-8-10 20:54 编辑

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:
                  slongest_start = sub_start
                  longestsub_len = sub_len
                  break
      s = s

      return s

liuzhengyuan 发表于 2022-8-10 21:37:15

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


超出时间限制
输入
"uhrfjotnewtodhmbplsaolnpcdaohiytmfllukijouxipvqohtsgxbtfoxyfkfczkfwhzimbefiohmtimrcxbpgcxogystdkcqujvbxsgirpccdnvejtljftwkdpsqpflzwruwwdzovsbmwbcvlftkjnxqaguvtsycylqzquqkbnybnbaeahbxejhphwrpmymcemuhljwtuvxefqfzjhskuqhifydkxpnfwfxkpeexnjltfqwfvchphmtsrsyayxukvmlqodshqwbeaxhcxdbssnrdzvxtusngwqdxvluauphmmbwmgtazjwvolenegwbmjfwprfuswamyvgrgshqocnhirgyakbkkggviorawadzhjipjjgiwpelwxvtaegauerbwpalofrbghfhnublttqtcmqskcocwwwxpnckrnbepusjyohsrretrqyvgnbezuvwmzizcefxyumtdwnqjkgsktyuacfpnqocqjxcurmipjfqmjqrkdeqsfseyigqlwmzgqhivbqalcxhlzgtsfjbdbfqiedogrqasgmimifdexbjjpfusxsypxobxjtcwxnkpgkdpgskgkvezkriixpxkkattyplnpdbdifforxozfngmlgcunbnubzamgkkfbswuqfqrvzjqmlfqxeqpjaqayodtetsecmfbplscmslpqiyhhykftzkkhshxqvdwmwowokpluwyvavwvofwqtdilwqjgrprukzyhckuspyzaoe"

liuzhengyuan 发表于 2022-8-10 21:40:30

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

超出时间限制
输入
"civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

liuzhengyuan 发表于 2022-8-10 21:45:15

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


第一个代码：
解答错误：
输入：
"a"
输出：
null
预期结果：
"a"
第二个代码：
输入：
"ac"
输出：
""
预期结果：
"a"

hornwong 发表于 2022-8-10 22:00:42

看看

ba21 发表于 2022-8-11 11:34:41

本帖最后由 ba21 于 2022-8-11 11:58 编辑

搞个总结。
爆破：
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
            if tmpStr == tmpStr[::-1] and len(tmpStr)>len(res):
                res = tmpStr
               
    return res if res else s


高效：
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
            if tmpStr!=tmpStr[::-1]:
                tmpStr = s
               
            if tmpStr!=tmpStr[::-1]:
                break
            if len(tmpStr)>len(res):               
                res = tmpStr                  

            j+=1         

    return res

查看完整版本: Python：【新】每日一题 4