[LeetCode - Top Interview Questions(Easy, Python3)]Strings

전체 문제 목록

 

1. Reverse String

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

in-place라 reverse()를 사용했지만, slicing(s[:] = s[::-1])이 조금 더 빠르다.

 

2. Reverse Integer

class Solution:
    def reverse(self, x: int) -> int:
        
        if x == 0:
            return 0
        
        result = int(str(abs(x))[::-1])
        
        # 32-bit 정수 범위를 넘은 경우 0으로 처리
        if result<-2**31 or result>2**31-1:
            return 0
        
        # x가 양수면 result도 양수
        if x>0: 
            return result
        
        # x가 음수면 result도 음수
        return -1 * result

 

3. First Unnique Character in a String

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = collections.defaultdict(list)
        for idx in range(len(s)):
            count[s[idx]].append(idx)
        for char in s:
            if len(count[char]) == 1:
                return count[char][0]
        return -1

collections.defaultdict(list)를 선언하면 딕셔너리의 기본 값이 empty list가 된다. 즉 바로 append()를 사용할 수 있다.

첫번째 for문은 defaultdict인 count에 s(aka string)의 모든c(aka character)가 어떤 index에 위치해있는지 추가해주는 용도고, 두번째 for문은 s의 원소가 1번 쓰였으면(unique) 답을 return해주는 용도다.

unique character가 없다면 -1을 리턴해준다.

 

4. Valid Anagram

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

 

Anagram의 정의를 생각하면 쉽게 풀 수 있는 문제다.

같은 원소로 이루어져있으면 anagram이 맞고, 다르면 아니다.

 

5. Valid Palindrome

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

Palindrome은 'aba', 'uuupppuuu'와 같이 앞에서 읽어도, 뒤에서 읽어도 같은 문자열을 말한다.

알파벳 대분자는 소문자로 고려하고, 알파벳 소문자와 숫자(alphanumeric)를 빼고는 없는 것으로 치기때문에 re.sub를 사용해서 조건에 맞게 문자열을 변경해줬다.

그 후 앞뒤로 같은지 비교하기 위해 [::-1]을 사용해서 문자열을 거꾸로 뒤집어줬다.

 

6.  String to Integer (atoi)

class Solution:
    def myAtoi(self, s: str) -> int:
        
        s=s.strip()
        result = ''
        for char in s:
            if not result:
                if char.isdigit() or char in ['+', '-']: 
                    result=char
                else:
                    break
            else: 
                if char.isdigit():
                    result+=char
                else:
                    break
        
        # result가 ''거나 '+' 또는 '-'일 경우 0을 return해준다.
        # '+' 또는 '-'인 경우의 예시 -> 문자열 입력 s = '+-12'  
        if not result or result in ['+', '-']:
            return 0
        
        # int(result)가아니라 int(float(result))를 한 이유는 아래 이미지 참고
        result = int(float(result))
        # 32-bit integer 범위를 넘어갈 경우
        if result < -2**31:
            return -2**31
        if result > 2**31-1:
            return 2**31-1
    
        return result

int(float(result))를 한 이유

 

 

7.  Implement strStr()

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        try:
            return haystack.index(needle)
        except:
            return -1

 

8. Count and Say

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        
        s = self.countAndSay(n-1)
        result = ''
        cnt, idx = 1, 1
        while idx < len(s)+1:
            if idx < len(s) and s[idx] == s[idx-1]:
                cnt += 1
            else:
                result += str(cnt)+s[idx-1]
                cnt = 1
            idx += 1
        return result

n의 결과는 n-1에 의존하므로 재귀를 사용했다.

 

9. Longest Common Prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        answer = ''
        flag = True
        length = min(map(len, strs))
    
        for idx in range(length):
            elem = {str[idx] for str in strs}
            if idx == 0 and len(elem) == 1:
                answer = elem.pop()
            elif len(elem) != 1:
                flag = False
            elif len(elem) == 1 and flag:
                answer += elem.pop()
        return answer

공통 접두사를 찾는 문제다.

strs의 원소 중 가장 길이가 가장 짧은 원소의 길이를 사용해서 문제를 풀었다.