首页 文章

回文子串

提问于
浏览 次
-1

给定两个字符串 A 和 B ，每个字符串由小写字母组成，是否可以选择一些非空字符串s1和s2，其中s1是A的子字符串，s2是B的子字符串，使得s1 s2是回文字符串 . 这里'+'表示字符串之间的串联 .

For example:

Case 1:

A='abc'
B='abc'

解决方案选择s1和s2的一种可能方法是s1 =“ab”，s2 =“a”使得s1 s2，即“aba”是回文 .

Case 2:
A='a'
B='b'

解决方案：没有可能的方法来选择s1和s2，使得s1 s2是回文 .

注意：如果可能，打印'是'否则打印'否'在两个字符串之间找到回文子串的算法是什么？

python string algorithm palindrome

2 回答

  • 2

    两个字符串有一个共同的字母是必要的（并且足够） .

    def test(a, b):
    return not set(a).isdisjoint(set(b))
    回复于
  • 0

    该程序为您发布的问题提供了相当好的结果 .

    #palindromic substrings in Python
s1='potter'
s2='topper'
count=0
print('substring  substring    allowed \n of s1 \t   of s2\tpalindromes')
for m in range(len(s1)):
   for n in range(m+1,len(s1)+1):   # n > m
    subs1=s1[m:n]               # substring of s1
    l = n-m                     # length of subs1
    print (subs1,'.................................')
    for r in range(len(s2)-l+1):
        subs2=s2[r:r+l]
        print('\t',subs2)
        if subs1==subs2[::-1]:  # string reversal
            print ('\t\t\t',subs1+subs2)
            count=count+1
if count==0:
    print ('No')
else:
    print('Yes')

    我在这里基本上做的是获取s1的子串 . 子串的长度逐渐增加，如'p'，'po'，'pot'，'pott'，'potte'，'potter' . 并且对应于s1的每个子字符串，我们检查来自另一个字符串s2的相等长度的子字符串 . 输出的一部分如下所示：

    substring  substring    allowed 
 of s1      of s2      palindromes
p .................................
            t
            o
            p
                         pp
            p
                         pp
            e
            r
po .................................
           to
           op
                        poop
           pp
           pe
           er
pot .................................
           top
                        pottop
           opp
           ppe
           per
 :          :              :
 :          :              :

    例如，对应于s1中的'pot'，我们在s2中得到'top'，'opp'，'ppe'，'per'，其长度与'pot'相同 . 但只有'顶部'反转才能回到'底池' . 因此，当'pot'与'top'连接时，它会形成一个回文 . 类似地，可以从这两个词中获得的其他回文是'pp'，'poop'，'pottop'，'oo'，'otto'，'tt'，'ee'和'rr' . 但我的程序没有解决制作奇数字母的回文问题 .

    回复于

相关问题