[PYTHON] Python : 단어 내에서 가장 긴 문장 검색 및 단어 / 문자열 내의 문장 검색
PYTHONPython : 단어 내에서 가장 긴 문장 검색 및 단어 / 문자열 내의 문장 검색
그래서 여기에 내가 단어 안에 palindromes을 찾기 위해 작성한 코드가 있습니다 (단어 자체 안에 단어가 있는지 여부를 확인하기 위해) 조건 : 문자 사이의 공백은 계산되고 무시되지 않습니다. 예 : 그러나 튜바는 회문이지만 기술적으로 관련된 공간으로 인해 현재는 그렇지 않습니다. 그래서 그것이 기준입니다.
위의 내용을 기반으로 다음 코드가 일반적으로 작동해야합니다. 이 코드가 오류를 일으키는 지 확인하기 위해 다른 테스트를 통해 스스로 시도 할 수 있습니다.
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
그리고 여기에는 그것의 존재하지 않는 버전이 있습니다. 내 말은 중간부터 시작해서 처음부터 반복하여 문자를 검색하고, 문자가 동일한 문자인지 확인하여 문자의 각 상위 및 하위 색인을 확인함으로써 문장 검색을 시도하는 것입니다. 그들은 그때 나는 정기적 인 palindrome 수표 같은 palindrome 있는지 확인입니다. 여기 내가 한 일이있다.
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 () 재미 :
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 : 두 번째 코드를 최적화하고 싶습니다. 어떤 입력?
Q3 : 여러 번 반복하는 My First 코드보다 훨씬 효율적인 코드가 더 나은 접근 방법은 무엇입니까?
해결법
-
==============================
1.당신의 솔루션은 나에게 조금 복잡해 보인다. 가능한 모든 하위 문자열을보고 개별적으로 확인하십시오.
당신의 솔루션은 나에게 조금 복잡해 보인다. 가능한 모든 하위 문자열을보고 개별적으로 확인하십시오.
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)), resultstext.index ()는 가장 긴 회문의 첫 번째 항목 만 찾으므로 마지막 항목을 원하면 text.rindex ()로 바꾸십시오.
-
==============================
2.다음 함수는 주어진 문자열에 포함 된 가장 긴 회문을 반환합니다. 이 답변에서 제안한대로 itertools를 사용한다는 점이 약간 다릅니다. 조합 생성을 추상화하는 데 가치가 있습니다. 그것의 시간 복잡성은 분명히 여전히 입방체입니다. 색인 및 / 또는 문장의 목록을 반환하는 데 필요할 때마다 쉽게 수정할 수 있습니다.
다음 함수는 주어진 문자열에 포함 된 가장 긴 회문을 반환합니다. 이 답변에서 제안한대로 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 -
==============================
3.
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)) -
==============================
4.재귀 적 솔루션이 마음에 들면, 재귀 버전을 작성했습니다. 또한 직관적입니다.
재귀 적 솔루션이 마음에 들면, 재귀 버전을 작성했습니다. 또한 직관적입니다.
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 -
==============================
5.다음은 가장 긴 회문 하위 문자열을 찾는 데 사용할 수있는 코드입니다.
다음은 가장 긴 회문 하위 문자열을 찾는 데 사용할 수있는 코드입니다.
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) -
==============================
6.
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 -
==============================
7.이 문자열 인자 's'에서 maxpalindrome (s)으로 함수 이름을 만들었습니다. 이 함수는 가능한 가장 긴 회문 하위 문자열과 하위 문자열의 길이를 반환합니다.
이 문자열 인자 's'에서 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 -
==============================
8.다음은 P. Norvig의 우수한 온라인 코스 디자인 프로그램에서 가져온 깨끗하고 간단한 접근 방법입니다. 문자열의 모든 문자를 반복하고 문자열을 왼쪽과 오른쪽으로 모두 "확장"하려고 시도합니다.
다음은 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) -
==============================
9.
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) -
==============================
10.
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 -
==============================
11.나는 해결책이 복잡해 보일지도 모른다는 것에 동의해야한다. (가장 큰 회상이 carac이어야하는 'character'에서 예를 들어 사이의 문자들을 고려한) 서브 시퀀스에서 가장 큰 palindrome을 찾는 최선의 해결책은 다음과 같다.
나는 해결책이 복잡해 보일지도 모른다는 것에 동의해야한다. (가장 큰 회상이 carac이어야하는 'character'에서 예를 들어 사이의 문자들을 고려한) 서브 시퀀스에서 가장 큰 palindrome을 찾는 최선의 해결책은 다음과 같다.
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_palidormea가 배열 인 경우이 솔루션은 재귀를 사용하고 동적 프로그래밍
-
==============================
12.중첩 루프 사용 :
중첩 루프 사용 :
for x in range(len(body)): for y in range(len(body)): ...
from https://stackoverflow.com/questions/17217473/python-search-longest-palindromes-within-a-word-and-palindromes-within-a-word-s by cc-by-sa and MIT license
'PYTHON' 카테고리의 다른 글
| [PYTHON] 여러 문자열이있는 열에서 get_dummies 형식 데이터 프레임을 만드는 가장 빠른 방법 (0) | 2018.10.19 |
|---|---|
| [PYTHON] PyBrain을 사용한 신경망 훈련은 수렴하지 않습니다. (0) | 2018.10.19 |
| [PYTHON] 파이썬 def 함수 : 함수의 끝을 어떻게 지정합니까? (0) | 2018.10.19 |
| [PYTHON] Python : 클래스를 반복 가능하게 만든다. (0) | 2018.10.19 |
| [PYTHON] 팬더 데이터 프레임을 시리즈로 변환 (0) | 2018.10.19 |