Python: поиск самых длинных палиндромов в слове и палиндромов в слове / строке
Итак, вот код, который я написал, чтобы найти палиндромы в слове (чтобы проверить, есть ли палиндромы в слове, включая само слово) Условие: пробелы между символами подсчитываются и не игнорируются. Пример: А, но туба - палиндром, но технически в пространствах, участвующих в настоящее время это не так. так что это критерии.
Исходя из вышеизложенного, следующий код обычно должен работать. Вы можете попробовать самостоятельно с различными тестами, чтобы проверить, если этот код дает какую-либо ошибку.
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'])
Теперь, считая мадам очень хорошим палиндромом, он должен работать, и есть много случаев, которые я не проверял сам, чтобы выяснить, какие другие законные палиндромы он не обнаруживает.
Q1: почему это иногда не обнаруживает?
Q2: Я хотел бы оптимизировать свой второй код в этом отношении. Любые входы?
Вопрос 3. Какой лучший подход существует для гораздо более эффективного кода, чем мой первый код, который повторяется много раз?
17 ответов
Ваше решение кажется мне немного сложным. Просто посмотрите на все возможные подстроки и проверьте их индивидуально:
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(),
Следующая функция возвращает самый длинный палиндром, содержащийся в данной строке. Это просто немного отличается в том, что он использует itertools как предложено в этом ответе. Есть смысл абстрагироваться от генерации комбинации. Его временная сложность, очевидно, все еще кубическая. При необходимости его можно легко адаптировать для возврата индекса и / или списка палиндромов.
import itertools
def longest_palindrome(s):
lp, lp_len = '', 0
for start, stop in itertools.combinations(range(len(s)+1), 2):
ss = s[start:stop] # substring
if (len(ss) > lp_len) and (ss == ss[::-1]):
lp, lp_len = ss, len(ss)
return lp
Если вам нравится рекурсивное решение, я написал рекурсивную версию. Это также интуитивно понятно.
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
Ниже приведен код, который я написал для того же вопроса. Это может быть не очень оптимизировано, но работает как шарм. Довольно легко понять и для начинающих
def longestPalindrome(s):
pal = []
longestpalin = s
l = list(s)
if len(s)>0:
if len(s)==2:
p = l
if p[0]==p[1]:
return s
else:
return l[0]
else:
for i in range(0,len(l)):
for j in range(i+1,len(l)+1):
p = l[i:j]
if p == p[::-1]:
if len(p)>len(pal):
pal = p
p = ''.join(p)
longestpalin = p
return longestpalin
else:
return longestpalin
Решение Python 3: (не самое быстрое)
class Solution:
def longestPalindrome(self, s: str) -> str:
if s == "":
return ""
if len(s) == 1:
return s
if len(s) == 2:
if s == s[::-1]:
return s
else:
return s[0]
results = []
for i in range(len(s)):
for j in range(0, i):
chunk = s[j:i + 1]
if chunk == chunk[::-1]:
results.append(chunk)
if results:
return max(results, key=len)
else:
return s[0]
s='stresseddesserts'
out1=[]
def substring(x):
for i in range(len(x)):
a=x[i:]
b=x[:-i]
out1.append(a)
out1.append(b)
return out1
for i in range(len(s)):
substring(s[i:])
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]{'tresseddessert': 14, 'seddes': 6, 'esseddesse': 10, 'esse': 4, 'stressdesserts': 16, 'resseddesser': 12, 'edde': 4, 'sseddess': 8}
('подчеркнутые десерты', 16)
Я использовал грубую силу, чтобы проверить, что каждая возможная подстрока является палиндромом, и обновить самую длинную найденную длину. есть более быстрые реализации на leetcode, включая динамическое программирование
import java.util.List;import java.util.ArrayList;
// этот подход работает, но есть более быстрые реализации в коде leet // может тестировать строки для палиндромов в основном методе, выводить на терминал
class Solution {
public static void main (String [] args ) {
Solution test = new Solution();
// can test strings for palindromes here
System.out.println( test.longestPalindrome( "abcdracecarabcd" ));
System.out.println( test.longestPalindrome( "ottoracecar" ));
System.out.println( test.longestPalindrome( "a" ));
System.out.println( test.longestPalindrome( "123otto123" ));
System.out.println( test.longestPalindrome( "" ));
System.out.println( test.longestPalindrome( "" ));
}
public String longestPalindrome(String s) {
List<Pair> pairs = new ArrayList<Pair>();
String currentHighest = "";
// generate List of all possible subStrings (start character, and end character); there are n(n-1)/2 pair combinations.
for (int i=0;i<=s.length();i++){
int l = i;
for (int j=i+1; j <= s.length(); j++) {
int r = j;
pairs.add(new Pair(l,r));
}
}
// check if each possible substring is a palindrom and update the currentHighest found
for(Pair p: pairs) {
// System.out.println("start: " + p.L + " end: " + p.R);
if (s.substring(p.L, p.R).equals( new StringBuffer(s.substring(p.L, p.R)).reverse().toString())) {
if (s.substring(p.L, p.R).length() > currentHighest.length()) currentHighest = s.substring(p.L, p.R);
}
}
return currentHighest;
}
// inner class to define a Pair
class Pair {
int L;
int R;
Pair (int l, int r){
this.L = l;
this.R = r;
}
}
}
Вот код, который вы можете использовать для поиска самой длинной палиндромной подстроки:
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)
Я сделал имя функции как maxpalindrome(s) в этом одном строковом аргументе '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
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)
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))
Вот еще один простой и понятный подход, взятый из отличного онлайн-курса " Дизайн компьютерных программ " П. Норвига. Он перебирает все символы в строке и пытается "увеличить" строку как влево, так и вправо.
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)
Это можно определить с помощью окна, наведенного на слово.Поскольку нас интересует только поиск самого длинного палиндрома, мы можем начать размер окна с размера самого слова и постепенно уменьшать его, проверяя все возможности фрагментов. которые прикрыты окном. Мы можем остановить алгоритм, когда найдем первый кусок палиндрома, который также будет самым длинным палиндромом в данном слове.
word = input("Word:").lower()
window_size = len(word)
found = False
while window_size > 1 and not found:
start = 0
while start <= len(word) - window_size and not found:
window = word[start:start+window_size]
if window[::-1] == window:
print("Longest Palindrome :" , window)
found = True
start += 1
window_size -= 1
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
def longestPalindrome(s):
temp = ""
for i in range(len(s)):
for j in range(len(s)-1,i-1,-1):
if s[i] == s[j]:
m = s[i:j+1]
if m == m[::-1]:
if len(temp) <= len(m):
temp = m
return temp
Я должен согласиться с тем, что решение может показаться сложным, я думаю, что лучшее решение - найти самый большой палиндром в подпоследовательности (учитывая символы между ними, например, в "символе", самый большой палиндром должен быть carac):
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 - массив, это решение использует рекурсию и динамическое программирование.
Используйте вложенный цикл:
for x in range(len(body)):
for y in range(len(body)):
...