Python: Word/string ішіндегі сөздер мен палиндромдардың ішіндегі ең ұзақ палиндромдарды іздеу

Міне, мен сөзбен айтқанда, палиндромаларды табу үшін жазған код (сөздің өзі ішіндегі сөздің ішінде палиндромдардың бар-жоғын тексеру үшін) Шарт: бос орындар арасындағы сандар есептеледі және еленбейді Мысал: Туба - бұл палиндром, бірақ техникалық тұрғыда кеңістіктерге байланысты. сондықтан бұл критерийлер.

Жоғарыда айтылғандарға негізінен келесі код жұмыс істеуі керек. Сіз бұл кодын кез-келген қате жібере ме, жоқ па екенін тексеру үшін әртүрлі сынақтармен өзіңізді сынап көріңіз.

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

Міне, оның нашар нұсқасы. Мен айтып өткендей, ортасынан бастауға тырысып, палиндромаларды басынан бастап қайталап, әр таңбаның жоғары және төменгі индекстерін тексеріп, олардың теңдесі жоқ екенін тексеріп көрейін. егер олар болса, онда палиндромның палиндромды тұрақты тексеру сияқты еместігін тексеремін. Міне, мен жасадым

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() 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'])

Және критерийлер/жағдай бойынша:

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'])

Кейде ол мүлде жұмыс істемейді:

    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'])

Міне, ханым - бұл өте жақсы палиндром, ол жұмыс істеуі керек және көптеген басқа жағдайлар бар, ол мен анықтаған басқа заңды палиндромдардың қандай екенін білмеймін.

1-сұрақ: Неліктен кейде анықталмайды?

2-ші сұрақ: Осы мәселе бойынша екінші кодты оңтайландыруды қалаймын. Кез келген кіріс?

3-ші сұрақ: Көптеген уақытты қайтаратын бірінші кодқа қарағанда әлдеқайда тиімді кодты не жақсы жаққа қарай қолдануға болады?

0

11 жауаптар

Сіздің шешіміңіз мен үшін күрделі болып көрінеді. Мүмкін болатын ішкі жолдардың барлығын қарап, оларды жеке тексеріңіз:

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() will only find the first occurrence of the longest palindrome, so if you want the last, replace it with text.rindex().

10
қосылды
Иә, бұл әйтпесе esp. 2-ші код үшін, func findlet() функциясын пайдаланып, осы әріптің барлық индекстерін іздеу үшін word.i асқындырылған. Өте жақсы
қосылды автор user2290820, көзі
бірақ мен кодты және менің 1-коды бірдей жасайтын диапазонға (сөзді) (len (сөз)) ғана өзгерту керек екенін түсіндім. Меніңше, егер бар болса, неғұрлым тиімді шешімдерді іздеңіз деп ойлаймын
қосылды автор user2290820, көзі

Ішкі циклды қолданыңыз:

for x in range(len(body)):
    for y in range(len(body)):
    ...
3
қосылды
Бұл бірдеңе жасай алады, бірақ мәселені кез-келген жолмен қалай шешетіні анық емес.
қосылды автор Jeffrey Bosboom, көзі

Мен келісуім керек, бұл шешім күрделі болып көрінуі мүмкін, мен ең жақсы шешім деп ойлаймын, ең үлкен палиндромды кейіннен табуға болады (мысалы, «кейіпкердің» ең үлкен палиндромы «карак» болуы керек)

def find_char_backwards(a, c):
for i in range(len(a) - 1, -1,-1):
    if a[i] == c:
        index=i
        return True, index

return False, 0

def longest_palindorme(a):
if len(a) < 2:
    return a
else:
    c=a[0]
    (exist_char,index) = find_char_backwards(a[1:],c)
    if exist_char:
        palindrome=[c] + longest_palindorme(a[1:index+1]) + [c]
    else:
        palindrome=[]
    rest_palidorme=longest_palindorme(a[1:])

if len(palindrome)>len(rest_palidorme):
    return palindrome
else:
    return rest_palidorme

A массасы болса, бұл шешім рекурсияны және динамикалық бағдарламалауды қолданады

2
қосылды

Егер сізге рекурсивті шешім ұнаса, мен рекурсивті нұсқаны жаздым. Бұл сондай-ақ интуитивті.

def palindrome(s):
  if len(s) <= 1:
    return s
  elif s[0] != s[-1]:
    beginning_palindrome = palindrome(s[:-1])
    ending_palindrome = palindrome(s[1:])
    if len(beginning_palindrome) >= len(ending_palindrome):
      return beginning_palindrome
    else:
      return ending_palindrome
  else:
    middle_palindrome = palindrome(s[1:-1])
    if len(middle_palindrome) == len(s[1:-1]):
        return s[0] + middle_palindrome + s[-1]
    else:
        return middle_palindrome
0
қосылды
value ="Madamaaamadamaaaacdefgv"
longestPalindrome =""
lenght =0;
for i in range(len(value)):
        for j in range(0, i):
            array = value[j:i + 1]
            if (array == array[::-1] and len(longestPalindrome) < len(array)):
                longestPalindrome =array
print(longestPalindrome)
0
қосылды
a = "xabbaabba"  # Provide any string

count=[]
for j in range(len(a)):
    for i in range(j,len(a)):
        if a[j:i+1] == a[i:j-1:-1]:      
            count.append(i+1-j)

print("Maximum size of Palindrome within String is :", max(count))
0
қосылды
Кодтың тек жауаптары өздігінен пайдалы емес. Бұл мәселені қалай/неге жауап беретінін түсіндіретін кейбір мәліметтерді қосуға көмектеседі.
қосылды автор SiHa, көзі
Бұл код бұл мәселені шешуге көмектесуі мүмкін, бірақ ол неге және/немесе қалай деген сұраққа жауап бермейді. Бұл қосымша контексті қамтамасыз ету оның ұзақ мерзімді білім беру құндылығын едәуір жақсартады. Түсініктеме қосу үшін сіздің жауапыңызды өңдеуіңіз сұраймыз, соның ішінде қандай шектеулер мен жорамалдар қолданылады.
қосылды автор Toby Speight, көзі

Ең ұзын палиндромикалық субстринді табу үшін пайдалануға болатын код:

string = "sensmamstsihbalabhismadamsihbala"
string_shortener = ""
pres = 0
succ = 3
p_temp=0
s_temp=0
longest = ""
for i in range(len(string)-2):
    string_shortener = string[pres:succ]
    if(string_shortener==string_shortener[::-1]):
       p_temp = pres
       s_temp = succ
       for u in range(1000):
           p_temp-=1
           s_temp +=1
           string_shortener = string[p_temp:s_temp]
           if(string_shortener == string_shortener[::-1]):
                if len(string_shortener)>len(longest):
                    longest = string_shortener
            else:
                break
    pres+=1
    succ+=1
print(longest)
0
қосылды
кодты бере отырып, ешқандай түсіндірмей стек толып тастау стандарттарына сай болмайды
қосылды автор Tanuj Yadav, көзі
inputStr = "madammmdd"
outStr = ""
uniqStr = "".join(set(inputStr))
flag = False
for key in uniqStr:
   val = inputStr.count(key)
   if val % 2 !=0:
      if not flag:
         outStr = outStr[:len(outStr)/2]+key+outStr[len(outStr)/2:]
         flag=True
      val-=1
   outStr=key*(val/2)+outStr+key*(val/2)
print outStr
0
қосылды

Мен осы функцияны бір дәлелдің '' 'дәлелінде maxpalindrome (s) ретінде жасадым. Бұл функция ең ұзын палиндром ішкі жолын және ішкі жолдың ұзындығын қайтарады ...

def maxpalindrome(s):
if len(s) == 1 or s == '':
    return str(len(s)) + "\n" + s
else:
    if s == s[::-1]:
        return str(len(s)) + "\n" + s
    else:
        for i in range(len(s)-1, 0, -1):
            for j in range(len(s)-i+1):
                temp = s[j:j+i]
                if temp == temp[::-1]:
                    return str(len(temp)) +"\n"+temp
0
қосылды
бұл жоғарыда аталған шешім
қосылды автор Abhishek Yadav, көзі

Мұнда басқа таза және қарапайым әдіс, тамаша онлайн курстан алынған Дизайн Компьютерлік бағдарламаларды P. Norvig. Ол жолдағы барлық таңбалардың үстінен жылжиды және жолды солға және оңға «өсіруге» тырысады.

def longest_sub_palindrome_slice(text):
    "Return (i,j) such that text[i,j] is the longest palindrome in text"
    if text == '': return (0, 0)
    def length(slice): a,b = slice; return b-a
    candidates = [grow(text, start, end)
                 for start in range(len(text))
                 for end in (start, start + 1)]
    return max(candidates, key=length)

def grow(text, start, end):
    "Start with a 0- or 1- length palindrome; try to grow a bigger one"
    while (start > 0 and end < len(text)
           and text[start-1].upper() == text[end].upper()):
        start -= 1; end += 1
    return (start, end)
0
қосылды