[已解决]Python：每日一题 292

zltzlt

今天的题目：

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。返回可以用这种方式转换成为的最短回文串。

示例 1：

输入："aacecaaa"
输出："aaacecaaa"

示例 2：

输入："abcd"
输出："dcbabcd"

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2019-12-20 19:56:01

变形的kmp搜索

1. def fun292(s):
   
2.     def nextarr(s):
   
3.         l=len(s)//2
   
4.         ret=[-1,0]
   
5.         p=0
   
6.         for q in range(1,l-1):
   
7.             while (p!=-1 and s[p]!=s[q]):
   
8.                 p=ret[p]
   
9.             p+=1
   
10.             ret.append(p);
    
11. 
    
12.         for i in range(1,l):
    
13.             if (s[i]==s[ret[i]]):
    
14.                 ret[i]=ret[ret[i]]
    
15.         return ret
    
16.     next=nextarr(s)
    
17.     p=0
    
18.     q=-1
    
19.     while (p-q<len(s)):
    
20.         while (p!=-1 and s[p]!=s[q]):
    
21.             p=next[p]
    
22.         q-=1
    
23.         p+=1
    
24.     if (p+q+1==0):
    
25.         return s
    
26.     return  s[:p+q:-1]+ s

复制代码

跳转到最佳答案楼层

Croper

变形的kmp搜索

1. def fun292(s):
   
2.     def nextarr(s):
   
3.         l=len(s)//2
   
4.         ret=[-1,0]
   
5.         p=0
   
6.         for q in range(1,l-1):
   
7.             while (p!=-1 and s[p]!=s[q]):
   
8.                 p=ret[p]
   
9.             p+=1
   
10.             ret.append(p);
    
11. 
    
12.         for i in range(1,l):
    
13.             if (s[i]==s[ret[i]]):
    
14.                 ret[i]=ret[ret[i]]
    
15.         return ret
    
16.     next=nextarr(s)
    
17.     p=0
    
18.     q=-1
    
19.     while (p-q<len(s)):
    
20.         while (p!=-1 and s[p]!=s[q]):
    
21.             p=next[p]
    
22.         q-=1
    
23.         p+=1
    
24.     if (p+q+1==0):
    
25.         return s
    
26.     return  s[:p+q:-1]+ s

复制代码

_2_

先抢个沙发再说

zltzlt

_2_ 发表于 2019-12-20 20:36
先抢个沙发再说

先上传代码再说

Unicorn#

1. def solve(s):
   
2.     def reverse_check(s):
   
3.         for i in range(len(s)//2):
   
4.             if s[i] != s[-1-i]:
   
5.                 return False
   
6.         return True
   
7.     if reverse_check(s):
   
8.         return s
   
9.     else:
   
10.         for i in range(1, len(s)):
    
11.             if reverse_check(s[:-i]):
    
12.                 return ''.join(reversed(s[-i:])) + s

复制代码

冬雪雪冬

1. def fun(str1):
   
2.     str2 = str1[::-1]
   
3.     for i in range(len(str1)):
   
4.         if str2[i:] == str1[0: len(str1)  - i]:
   
5.             return str2[:i] + str1

复制代码

zltzlt

Unicorn# 发表于 2019-12-20 20:45

输入 "a" * 40000 超时

zltzlt

冬雪雪冬 发表于 2019-12-20 20:52

解答错误

输入：""
输出；None
预期结果：""

冬雪雪冬

zltzlt 发表于 2019-12-20 21:06
解答错误

输入：""

加上一行

1. def fun(str1):
   
2.     str2 = str1[::-1]
   
3.     for i in range(len(str1)):
   
4.         if str2[i:] == str1[0: len(str1)  - i]:
   
5.             return str2[:i] + str1
   
6.     return ''

复制代码

peicd

1. def solve(s):
   
2.     temp=''
   
3.     for each in s[::-1]:
   
4.         m=temp+s
   
5.         if m==m[::-1]:
   
6.             return m
   
7.         else:
   
8.             temp+=each
   
9.     return s

复制代码

阴阳神万物主

改了一改，康康这回如何。

1. def solve(s:str)->str:
   
2.     '''
   
3.     用最短方式在前方添加字符使其成为回文
   
4.     '''
   
5.     le = len(s)
   
6.     rs = ''.join(reversed(s))
   
7.     for d in range(le):
   
8.         #print('调试',s[:le-d],rs[d:])
   
9.         if s[:le-d] == rs[d:]:
   
10.             break
    
11.     return rs[:d] + s
    
12. 
    
13. if __name__ == '__main__':
    
14.     '''
    
15.     print('示例1 输出：',solve("aacecaaa"))
    
16.     print('示例2 输出：',solve('abcd'))
    
17.     print('自测 输出：',solve('aca'))
    
18.     '''
    
19.     import random
    
20.     def get(n:int):
    
21.         alpha = 'abcdefghijklmnopqrstuvwxyz'
    
22.         for i in range(n):
    
23.             yield random.choice(alpha)
    
24.     a = solve(''.join(get(40000)))
    

复制代码

这回感觉可以

1. >>> c = ''.join(get(40000))
   
2. >>> if True:
   
3.         a = time.perf_counter()
   
4.         solve(c)
   
5.         b = time.perf_counter()
   
6. 
   
7.         1001行的内容被折叠
   
8. 
   
9. >>> b-a
   
10. 0.6628862999999967
    
11. >>>

复制代码

Unicorn#

..

danteer

1. def solve(s):
   
2.     count = 0
   
3.     while True:
   
4.         if s == s[::-1]:
   
5.             return s
   
6.         else:
   
7.             s = s[:count] + s[-count-1] + s[count:]
   
8.             count += 1

复制代码

Unicorn#

zltzlt 发表于 2019-12-20 21:05
输入 "a" * 40000 超时

这个不能怪我鸭
是在IDLE中显示结果超时，但是计算不会超时的

1. ans = solve('a'*40000)

复制代码

这样如果不把结果显示出来，就一点毛病都没有的

沙里爬

1. def is_huiwenchuan(str):
   
2. 
   
3.     list1 = list(str)
   
4.     list2 =list1.copy()
   
5.     list1.reverse()
   
6.     if list1 == list2:
   
7.         return True
   
8.     else:
   
9.         return False
   
10. 
    
11. def huiwenchuan(str):
    
12. 
    
13.     if is_huiwenchuan(str):
    
14.         return str
    
15.     #原始回文串长度
    
16.     lenth = len(str)
    
17. 
    
18.     k = 0
    
19.     for i in range(1,lenth):
    
20.         str1 = str[:-i]
    
21.         if is_huiwenchuan(str1):
    
22.             k = i
    
23.             break
    
24. 
    
25.     lst = list(str)
    
26.     str2 = ''
    
27.     for i in range(k):
    
28.         str2 += lst[lenth-i-1]
    
29. 
    
30.     str = str2 +str
    
31. 
    
32.     return str

复制代码

fengo0

def solve(str1):
    str2 = str1[::-1]
    length = len(str1)

    for i in range(length):
        if str1[:length-i] == str2[i:]:
            return str2[:i] + str1

str1 = input('请输入文本：')
print(solve(str1))

zltzlt

Unicorn# 发表于 2019-12-20 21:26
这个不能怪我鸭
是在IDLE中显示结果超时，但是计算不会超时的

就是计算超时，我没有在 IDLE 中测试。

零0℃度

1. def f292(s):
   
2.     i = 1
   
3.     n = len(s)
   
4.     while i < n:
   
5.         if s[-i::-1] != s[:n+1-i]:
   
6.             i+=1
   
7.         else:
   
8.             break
   
9.     return s[-1:-i:-1] + s

复制代码

18463102026

1. def fun(lst):
   
2.     if lst == lst[::-1]:
   
3.         return lst
   
4.     for i in range(1,len(lst)+1):
   
5.         if lst[:-i] == lst[-1-i::-1]:
   
6.             return lst[:-i-1:-1]+lst
   
7.         i += 1

复制代码

TJBEST

我写了一个程序 大概20分钟，可能有瑕疵

1. def fun292(inputStr):
   
2.     def isHuiwen(example):
   
3.         lenth = len(example)
   
4.         state = True
   
5.         for i in range(0,lenth//2):
   
6.             if example[i] != example[lenth-1-i]:
   
7.                 state = False
   
8.                 break
   
9.         return state
   
10.     if inputStr == '':
    
11.         return ''
    
12.     else:
    
13.         strLenth = len(inputStr)
    
14.         index_Hui = 0
    
15.         for index in range(0,strLenth):
    
16.             if isHuiwen(inputStr[0:strLenth-index]):
    
17.                 index_Hui = strLenth-index -1
    
18.                 break
    
19.         first = inputStr[(strLenth-1):index_Hui:-1]
    
20.         second = inputStr[0:index_Hui+1]
    
21.         third = inputStr[(index_Hui+1):strLenth]
    
22.      #   print(first)
    
23.       #  print(second)
    
24.         #print(third)
    
25.         return first + second + third

复制代码