Python:在单词内搜索最长回文，在单词/字符串内搜索回文 [英] Python: search longest palindromes within a word and palindromes within a word/string

问题描述

因此，这是我编写的用于查找单词内回文的代码(用于检查单词内是否包括单词本身在内的回文) 条件:字符之间的空格被计算并且不被忽略 示例:a但是，大号是回文，但从技术上讲，由于涉及空间，现在不是.这就是标准.

So here is a code i have written to find palindromes within a word (To check if there are palindromes within a word including the word itself) Condition: spaces inbetween characters are counted and not ignored Example: A but tuba is a palindrome but technically due to spaces involved now it isn't. so that's the criteria.

基于上述内容，通常可以使用以下代码.您可以尝试进行不同的测试，以检查此代码是否提供任何错误.

Based on above, the following code usually should work. You can try on your own with different tests to check out if this code gives any error.

def pal(text):
    """

    param text: given string or test
    return: returns index of longest palindrome and a list of detected palindromes stored in temp
    """
    lst = {}
    index = (0, 0)
    length = len(text)
    if length <= 1:
        return index
    word = text.lower()  # Trying to make the whole string lower case
    temp = str()
    for x, y in enumerate(word):
        # Try to enumerate over the word
        t = x
        for i in xrange(x):
            if i != t+1:
                string = word[i:t+1]
                if string == string[::-1]:
                    temp = text[i:t+1]
                    index = (i, t+1)
                    lst[temp] = index
    tat = lst.keys()
    longest = max(tat, key=len)
    #print longest
    return lst[longest], temp

这是已失效的版本.我的意思是，我试图从中间开始，并从头开始进行迭代，并通过检查字符是否相等来检查字符的每个较高和较低的索引，从而检测回文.如果他们是，那么我正在检查其回文检查是否像常规回文检查一样. 这是我所做的

And here is a defunct version of it. What I mean is I have tried to start out from the middle and detect palindromes by iterating from the beginning and checking for each higher and lower indices for character by checking if they are equal characters. if they are then i am checking if its a palindrome like a regular palindrome check. here's what I have done

def pal(t):
    text = t.lower()
    lst = {}
    ptr = ''
    index = (0, 0)
    #mid = len(text)/2
    #print mid
    dec = 0
    inc = 0
    for mid, c in enumerate(text):
        dec = mid - 1
        inc = mid + 1
        while dec != 0 and inc != text.index(text[-1]):
            print 'dec {}, inc {},'.format(dec, inc)
            print 'text[dec:inc+1] {}'.format(text[dec:inc+1])
            if dec<0:
                dec = 0
            if inc > text.index(text[-1]):
                inc = text.index(text[-1])
            while text[dec] != text[inc]:
                flo = findlet(text[inc], text[:dec])
                fhi = findlet(text[dec], text[inc:])
                if len(flo) != 0 and len(fhi) != 0 and text[flo[-1]] == text[fhi[0]]:
                    dec = flo[-1]
                    inc = fhi[0]
                    print ' break if'
                    break
                elif len(flo) != 0 and text[flo[-1]] == text[inc]:
                    dec = flo[-1]
                    print ' break 1st elif'
                    break
                elif len(fhi) != 0 and text[fhi[0]] == text[inc]:
                    inc = fhi[0]
                    print ' break 2nd elif'
                    break
                else:
                    dec -= 1
                    inc += 1
                    print ' break else'
                    break
            s = text[dec:inc+1]
            print ' s {} '.format(s)
            if s == s[::-1]:
                index = (dec, inc+1)
                lst[s] = index
            if dec > 0:
                dec -= 1
            if inc < text.index(text[-1]):
                inc += 1
    if len(lst) != 0:
        val = lst.keys()
        longest = max(val, key = len)
        return lst[longest], longest, val
    else:
        return index

findlet()有趣:

findlet() fun:

def findlet(alpha, string):
    f = [i for i,j in enumerate(string) if j == alpha]
    return f

有时可以正常工作:

pal('madem')
dec -1, inc 1,
text[dec:inc+1] 
 s m 
dec 1, inc 3,
text[dec:inc+1] ade
 break 1st elif
 s m 
dec 2, inc 4,
text[dec:inc+1] dem
 break 1st elif
 s m 
dec 3, inc 5,
text[dec:inc+1] em
 break 1st elif
 s m 
Out[6]: ((0, 1), 'm', ['m'])

pal('Avid diva.')
dec -1, inc 1,
text[dec:inc+1] 
 break 2nd if
 s avid div 
dec 1, inc 3,
text[dec:inc+1] vid
 break else
 s avid  
dec 2, inc 4,
text[dec:inc+1] id 
 break else
 s vid d 
dec 3, inc 5,
text[dec:inc+1] d d
 s d d 
dec 2, inc 6,
text[dec:inc+1] id di
 s id di 
dec 1, inc 7,
text[dec:inc+1] vid div
 s vid div 
dec 4, inc 6,
text[dec:inc+1]  di
 break 1st elif
 s id di 
dec 1, inc 7,
text[dec:inc+1] vid div
 s vid div 
dec 5, inc 7,
text[dec:inc+1] div
 break 1st elif
 s vid div 
dec 6, inc 8,
text[dec:inc+1] iva
 break 1st elif
 s avid diva 
dec 8, inc 10,
text[dec:inc+1] a.
 break else
 s va. 
dec 6, inc 10,
text[dec:inc+1] iva.
 break else
 s diva. 
dec 4, inc 10,
text[dec:inc+1]  diva.
 break else
 s d diva. 
dec 2, inc 10,
text[dec:inc+1] id diva.
 break else
 s vid diva. 
Out[9]: ((0, 9), 'avid diva', ['avid diva', 'd d', 'id di', 'vid div'])

根据我提出的条件/条件:

And based on the Criteria/Condition i have put:

pal('A car, a man, a maraca.')
dec -1, inc 1,
text[dec:inc+1] 
 break else
 s  
dec -1, inc 3,
text[dec:inc+1] 
 s a ca 
dec 1, inc 3,
text[dec:inc+1]  ca
 break if
 s a ca 
dec 2, inc 4,
text[dec:inc+1] car
 break else
 s  car, 
dec 3, inc 5,
text[dec:inc+1] ar,
 break else
 s car,  
dec 1, inc 7,
text[dec:inc+1]  car, a
 break 1st elif
 s a car, a 
dec 4, inc 6,
text[dec:inc+1] r, 
 break 1st elif
 s  car,  
dec 5, inc 7,
text[dec:inc+1] , a
 break 1st elif
 s ar, a 
dec 2, inc 8,
text[dec:inc+1] car, a 
 break 1st elif
 s  car, a  
dec 6, inc 8,
text[dec:inc+1]  a 
 s  a  
dec 5, inc 9,
text[dec:inc+1] , a m
 break else
 s r, a ma 
dec 3, inc 11,
text[dec:inc+1] ar, a man
 break else
 s car, a man, 
dec 1, inc 13,
text[dec:inc+1]  car, a man, 
 s  car, a man,  
dec 7, inc 9,
text[dec:inc+1] a m
 break else
 s  a ma 
dec 5, inc 11,
text[dec:inc+1] , a man
 break else
 s r, a man, 
dec 3, inc 13,
text[dec:inc+1] ar, a man, 
 break if
 s   
dec 8, inc 10,
text[dec:inc+1]  ma
 break if
 s  
dec 6, inc 4,
text[dec:inc+1] 
 break 1st elif
 s r 
dec 3, inc 5,
text[dec:inc+1] ar,
 break else
 s car,  
dec 1, inc 7,
text[dec:inc+1]  car, a
 break 1st elif
 s a car, a 
dec 9, inc 11,
text[dec:inc+1] man
 break else
 s  man, 
dec 7, inc 13,
text[dec:inc+1] a man, 
 break if
 s  
dec 5, inc 2,
text[dec:inc+1] 
 break 1st elif
 s c 
dec 1, inc 3,
text[dec:inc+1]  ca
 break if
 s a ca 
dec 10, inc 12,
text[dec:inc+1] an,
 break 1st elif
 s , a man, 
dec 4, inc 13,
text[dec:inc+1] r, a man, 
 break 1st elif
 s  car, a man,  
dec 11, inc 13,
text[dec:inc+1] n, 
 break 1st elif
 s  man,  
dec 7, inc 14,
text[dec:inc+1] a man, a
 s a man, a 
dec 6, inc 15,
text[dec:inc+1]  a man, a 
 s  a man, a  
dec 5, inc 16,
text[dec:inc+1] , a man, a m
 break else
 s r, a man, a ma 
dec 3, inc 18,
text[dec:inc+1] ar, a man, a mar
 break else
 s car, a man, a mara 
dec 1, inc 20,
text[dec:inc+1]  car, a man, a marac
 break else
 s a car, a man, a maraca 
dec 12, inc 14,
text[dec:inc+1] , a
 break 1st elif
 s an, a 
dec 9, inc 15,
text[dec:inc+1] man, a 
 break if
 s  
dec 7, inc 2,
text[dec:inc+1] 
 break 1st elif
 s c 
dec 1, inc 3,
text[dec:inc+1]  ca
 break if
 s a ca 
dec 13, inc 15,
text[dec:inc+1]  a 
 s  a  
dec 12, inc 16,
text[dec:inc+1] , a m
 break 1st elif
 s man, a m 
dec 8, inc 17,
text[dec:inc+1]  man, a ma
 break 1st elif
 s a man, a ma 
dec 6, inc 18,
text[dec:inc+1]  a man, a mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 14, inc 16,
text[dec:inc+1] a m
 break 1st elif
 s man, a m 
dec 8, inc 17,
text[dec:inc+1]  man, a ma
 break 1st elif
 s a man, a ma 
dec 6, inc 18,
text[dec:inc+1]  a man, a mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 15, inc 17,
text[dec:inc+1]  ma
 break 1st elif
 s a ma 
dec 13, inc 18,
text[dec:inc+1]  a mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 16, inc 18,
text[dec:inc+1] mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 17, inc 19,
text[dec:inc+1] ara
 s ara 
dec 16, inc 20,
text[dec:inc+1] marac
 break 1st elif
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 18, inc 20,
text[dec:inc+1] rac
 break 1st elif
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 19, inc 21,
text[dec:inc+1] aca
 s aca 
dec 21, inc 23,
text[dec:inc+1] a.
 break else
 s ca. 
dec 19, inc 23,
text[dec:inc+1] aca.
 break else
 s raca. 
dec 17, inc 23,
text[dec:inc+1] araca.
 break else
 s maraca. 
dec 15, inc 23,
text[dec:inc+1]  maraca.
 break else
 s a maraca. 
dec 13, inc 23,
text[dec:inc+1]  a maraca.
 break else
 s , a maraca. 
dec 11, inc 23,
text[dec:inc+1] n, a maraca.
 break else
 s an, a maraca. 
dec 9, inc 23,
text[dec:inc+1] man, a maraca.
 break else
 s  man, a maraca. 
dec 7, inc 23,
text[dec:inc+1] a man, a maraca.
 break else
 s  a man, a maraca. 
dec 5, inc 23,
text[dec:inc+1] , a man, a maraca.
 break else
 s r, a man, a maraca. 
dec 3, inc 23,
text[dec:inc+1] ar, a man, a maraca.
 break else
 s car, a man, a maraca. 
dec 1, inc 23,
text[dec:inc+1]  car, a man, a maraca.
 break else
 s a car, a man, a maraca. 
Out[8]: ((13, 16), ' a ', ['', ' a ', 'c', ' ', 'aca', 'ara', 'r'])

有时候，它根本不起作用:

Sometimes, it doesn't work at all:

    pal('madam')
    dec -1, inc 1,
    text[dec:inc+1] 
     s m 
    dec 1, inc 3,
    text[dec:inc+1] ada
     break 1st elif
     s m 
    dec 2, inc 4,
    text[dec:inc+1] dam
     break 1st elif
     s m 
    dec 3, inc 5,
    text[dec:inc+1] am
     break 1st elif
     s m 
    Out[5]: ((0, 1), 'm', ['m'])

现在，考虑到夫人女士是一个非常好的回文症，它应该可以工作，而且在很多情况下，我还没有进行自我测试以找出它没有发现的其他合法回文症.

Now considering madam is a very nice palindrome it should work and there are many cases which i haven't tested myself to find out what other legitimate palindromes it doesn't detect.

Q1:为什么有时无法检测到?

Q1: Why is it sometimes not detecting?

Q2:我想为此优化第二个代码.有输入吗?

Q2: I would like to optimize my second code for that matter. Any inputs?

Q3:有什么更好的方法可以使代码效率更高得多，而我的First代码需要多次迭代?

Q3: What better approach is there for a much much more efficient code than my First code which iterates many a times?

推荐答案

您的解决方案对我来说似乎有点复杂.只需查看所有可能的子字符串并单独检查它们即可:

Your solution seems a bit complicated to me. Just look at all of the possible substrings and check them individually:

def palindromes(text):
    text = text.lower()
    results = []

    for i in range(len(text)):
        for j in range(0, i):
            chunk = text[j:i + 1]

            if chunk == chunk[::-1]:
                results.append(chunk)

    return text.index(max(results, key=len)), results

text.index()仅会找到最长回文的第一个出现，因此，如果需要最后一个，则用text.rindex()替换它.

text.index() will only find the first occurrence of the longest palindrome, so if you want the last, replace it with text.rindex().

这篇关于Python:在单词内搜索最长回文，在单词/字符串内搜索回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！