[Python] 문자열 조작

Python 문자열 조작

출처 : 점프투파이썬 위키독스 https://wikidocs.net/4308

---

* 모든 문제는 leetcode에서 참조함*

---

Problem 1. 유효한 팰린드롬

https://leetcode.com/problems/valid-palindrome/

 

Solution 1. 브루트포스 방식

 

In [1]:

import re
import collections
class Solution_1():
    def valid_palindrome_1(string: str) -> bool: # 가장 먼저 떠오른 풀이
        string = string.lower()
        string = re.sub(r'^\w','',string) # 아래 두 풀이의 isalnum()은 브루트포스방식이지만 정규식 처리가 더 빠름
        return string == string[::-1] # 문자열의 [::-1]은 내부적으로 C로 구현되어 있어 속도 좋음
    
    def valid_palindrome_2(string: str) -> bool:
        # list 사용
        strs = []
        for char in string:
            if char.isalnum():
                strs.append(char.lower())
        while len(strs) > 1:
            if strs.pop(0) != strs.pop(): # list의 pop(0)은 O(n)
                return False
            # 인덴트 위치를 여기로 해서 return True를 하면 
            # 양쪽에서 한번만 일치해도 바로 else로 작동해서 
            # 다 확인하기 전에 True 반환하고 함수 종료됨
        return True
    
    def valid_palindrome_3(string: str) -> bool:
        # deque 사용
        strs: Deque = collections.deque()
        
        for char in string:
            if char.isalnum():
                strs.append(char.lower())
        while len(strs) > 1:
            if strs.popleft() != strs.pop(): # deque의 popleft()는 O(1)
                return False
        return True

 

 

In [2]:

# valid_palindrome_1
print(Solution_1.valid_palindrome_1('Hackers makes the Better-code!'))
print(Solution_1.valid_palindrome_1('A man, a plan, a canal: Panama'))

 

Out [2]:

False
False

 

 

In [3]:

# valid_palindrome_2
print(Solution_1.valid_palindrome_2('Hackers makes the Better-code!'))
print(Solution_1.valid_palindrome_2('A man, a plan, a canal: Panama'))

 

Out [3]:

False
True

 

 

In [4]:

# valid_palindrome_3
print(Solution_1.valid_palindrome_3('Hackers makes the Better-code!'))
print(Solution_1.valid_palindrome_3('A man, a plan, a canal: Panama'))

 

Out [4]:

False
True

 

---

Solution 2. Two pointer solution

In [5]:

class Solution_2:
    # 2 pointer 풀이
    def valid_palindrome_4(s: str) -> bool:
        l, r = 0, len(s)-1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l <r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l +=1; r -= 1
        return True

    # 2 pointer 풀이 2
    def valid_palindrome_5(s: str) -> bool:
        beg, end = 0, len(s) - 1
        while beg <= end:
            while not s[beg].isalnum() and beg < end: beg += 1
            while not s[end].isalnum() and beg < end: end -= 1
            if s[beg] == s[end] or s[beg].upper() == s[end].upper():
                beg, end = beg + 1, end - 1
            else:
                return False
        return True

 

 

In [6]:

print(Solution_2.valid_palindrome_4('Hackers makes the Better-code!'))
print(Solution_2.valid_palindrome_4('A man, a plan, a canal: Panama'))

 

Out [6]:

False
True

 

 

In [7]:

print(Solution_2.valid_palindrome_5('Hackers makes the Better-code!'))
print(Solution_2.valid_palindrome_5('A man, a plan, a canal: Panama'))

 

Out [6]:

False
True

 

---

Problem 2. 문자열 뒤집기

https://leetcode.com/problems/reverse-string/

 

Solution 1. Two pointer solution

 

In [8]:

def reverse_string_1(strs: list) -> None:
    left, right = 0, len(strs) - 1
    while left < right:
        strs[left], strs[right] = strs[right], strs[left]
        left += 1
        right -= 1

 

 

In [9]:

reverse_string_1(['h','e','l','l','o'])
reverse_string_1(['H','a','n','n','a','h'])

 

---

Solution 2. Pythonic solution : reverse()

In [10]:

def reverse_string_2(strs: list) -> None:
    strs.reverse()

 

 

In [11]:

reverse_string_2(['h','e','l','l','o'])
reverse_string_2(['H','a','n','n','a','h'])

 

---

Problem 3. 로그 파일 재정렬

https://leetcode.com/problems/reorder-data-in-log-files/

 

Solution 1. lambda and list + operator

 

In [12]:

def reorder_log_files(logs: list) -> list:
    letters, digits = [], []
    for log in logs:
        if log.split()[1].isdigit():
            digits.append(log)
        else:
            letters.append(log)
            
    # 2개의 키를 람다 표현식으로 정렬
    letters.sort(key = lambda x: (x.split()[1:], x.split()[0]))
    return letters + digits

 

 

In [13]:

logs = ['dig1 8 1 5 1', 'let1 art can', 'dig2 3 6', 'let2 own kit dig', 'let3 art zero']
reorder_log_files(logs)

 

 

Out[13]:

['let1 art can',
 'let3 art zero',
 'let2 own kit dig',
 'dig1 8 1 5 1',
 'dig2 3 6']

 

---

보충자료 1. lambda

lambda expression

- 식별자 없이 실행 가능한 함수
- 함수 선언 없이 하나의 식으로 함수를 단순하게 표현 가능
- 즉 간단하나 함수를 쉽게 선언하는 방법
- map, filter와 함께 쓰면 가독성이 떨어지니 주의
- 특별한 경우가 아니면 대부분 list comprehension을 활용

 

참고할 자료 : How to Use Python Lambda Functions – Real Python

---

보충자료 2. sort의 key options / sort와 sorted()의 차이

How to Use sorted() and sort() in Python – Real Python

---

Problem 4. 가장 흔한 단어

https://leetcode.com/problems/most-common-word/

 

Solution 1. 정규식 & Counter 객체

In [14]:

def most_common_word(paragraph: str, banned: list) -> str:
    words = [word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]
    
    counts = collections.Counter(words)
    return counts.most_common(1)[0][0]

 

 

In [15]:

most_common_word('Bob hit a ball, the hit BALL flew far after it was hit.', 'hit')

 

 

Out[15]:

'ball'

 

---

Problem 5. 그룹 애너그램

https://leetcode.com/problems/group-anagrams/

 

Solution 1. defaultdict 객체 & 정렬

In [16]:

import collections
def group_anagrams(strs: list) -> list:
    anagrams = collections.defaultdict(list)
    
    for word in strs:
        # 정렬 후 딕셔너리에 추가
        anagrams[''.join(sorted(word))].append(word)
    return list(anagrams.values())

 

 

In [17]:

group_anagrams(['eat','tea','tan','ate','nat','bat'])

 

 

Out[17]:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

 

---

Problem 6. 가장 긴 팰림드롬 부분 문자열

https://leetcode.com/problems/longest-palindromic-substring/

 

Solution 1. ✨✨중앙을 중심으로 확장하는 two poiter

In [18]:

def logest_palindrome(s: str) -> str:
    def expand(left: int, right: int) -> str:
        while left >= 0 and right <= len(s) and s[left] == s[right - 1]:
            left -= 1
            right += 1
        return s[left+1 : right-1]
    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

 

 

In [19]:

logest_palindrome('babad')

 

 

Out[19]:

'bab'

 

출처 : 파이썬 알고리즘 인터뷰