파이썬 알고리즘 인터뷰 | 6장. 문자열

마음에 드는(??)  풀이만 정리해보자

 

유효한 펠린드롬

def isPalindrome(self, s:str)->bool:
	s=s.lower
    s=re.sub('[^a-z0-9]','',s)
    return s == s[::-1]

영숫자만 걸러내도록 정규식으로 처리

[::-1]을 사용하면 리스트를 뒤집을 수 있음

 

문자열 뒤집기

def reverseStr(self, s:List[str])->None:
	s.reverse()

또한 문자열 슬라이싱을 이용한 s[:]=s[::-1]도 가능함

 

로그 파일 재정렬

def reorderLogFiles(self, logs: List[str]) -> List[str]:
	letters, digits = [], []
    for log in logs:
    	if log.split()[1].isdigit():
        	digits.append(log)
        else:
        	letters.append(log)
	letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits

로그의 가장 앞부분은 식별자이므로 식별자를 제외한 문자열 [1:]를 키로 하여 정렬한다.

문자가 동일한 경우 후순위로 식별자 [0]을 지정해 정렬하도록 람다표현식을 사용했다.

 

가장 흔한 단어

words = [word for word in re.sub(r'[^\w]',' ',paragraph)
	.lower().split()
    	if word not in banned]

cnt = collections.Counter(words)
return cnt.most_common(1)[0][0]

\w(단어 문자)가 아닌 모든 문자를 공백으로 치환함

banned에 포함되지 않은 단어들로만 words에 저장된다.

 

그룹 애너그램

anagrams = collections.defaultdict(list)

for word in strs:
	anagrams[''.join(sorted(word))].append(word)
return list(anagrams.values())

애너그램은 해당 문자열을 정렬하면 같은 값을 가지므로 그 값을 키로 사용하여 원래의 문자열을 값으로 딕셔너리에 넣는다.

딕셔너리의 값만 출력하면 된다.

 

가장 긴 팰린드롬 부분 문자열

def expand(left, right):
	while left >= 0 and right <len(s) and s[left] == s[right]:
		left -=1
    	right +=1
	return s[left+1:right]

if len(s)<2 or s==s[::-1]:
	return s

result = ''
for i in range(len(s)-1):
	result = max(result),
    			expand(i, i+1),
                expand(i, i+2),
                key = len)
return result

expand에서 팰린드롬 판별하면서 투포인터를 확장한다

s의 길이가 1이거나 뒤집어서 같으면 s를 그대로 리턴한다.

for문을 돌리면서 슬라이딩 윈도우처럼 처음에서 계속 우측으로 이동하면서 최댓값을 판별한다.