Python: Suche nach längsten Palindromen innerhalb eines Wortes und Palindromen innerhalb eines Wortes / einer Zeichenkette
Also hier ist ein Code, den ich geschrieben habe, um Palindrome innerhalb eines Wortes zu finden. (Um zu überprüfen, ob es Palindrome innerhalb eines Wortes gibt, einschließlich des Wortes selbst.) Bedingung: Leerzeichen zwischen Zeichen werden gezählt und nicht ignoriert zu Räumen, die jetzt betroffen sind, ist es nicht. Das ist also das Kriterium.
Basierend auf dem obigen Code sollte normalerweise der folgende Code funktionieren. Sie können auf eigene Faust verschiedene Tests durchführen, um festzustellen, ob dieser Code einen Fehler enthält.
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
Und hier ist eine nicht mehr existierende Version davon. Was ich meine ist, dass ich versucht habe, von der Mitte aus zu beginnen und Palindrome zu erkennen, indem ich von Anfang an iteriere und nach jedem höheren und niedrigeren Index nach Zeichen prüfe, indem ich prüfe, ob sie gleiche Zeichen sind. Wenn ja, dann überprüfe ich, ob es sich um ein Palindrom handelt, wie bei einem normalen Palindrom-Check. hier ist was ich getan habe
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 () Spaß:
def findlet(alpha, string):
f = [i for i,j in enumerate(string) if j == alpha]
return f
Manchmal funktioniert es:
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'])
Und basierend auf den Kriterien / Bedingungen, die ich angegeben habe:
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'])
Manchmal funktioniert es überhaupt nicht:
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'])
In Anbetracht der Tatsache, dass Madam ein sehr schönes Palindrom ist, sollte es funktionieren, und es gibt viele Fälle, die ich nicht selbst getestet habe, um herauszufinden, welche anderen legitimen Palindrome es nicht erkennt.
F1: Warum wird es manchmal nicht erkannt?
F2: Ich möchte meinen zweiten Code für diese Angelegenheit optimieren. Irgendwelche Eingaben?
F3: Welchen besseren Ansatz gibt es für einen viel effizienteren Code als meinen First-Code, der mehrmals wiederholt wird?