리트코드 문제 8, 10

8. String to Integer

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function). The algorithm for myAtoi(string s) is as follows:

• step1: Read in and ignore any leading whitespace.
• step2: Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
• step3:Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
• step4: Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
• step5: If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.
• step6: Return the integer as the final result.

입력: s = “ -42”

출력: -42

내 풀이

class Solution:
    def myAtoi(self, s: str) -> int:
        int_str = ''
        sign = 1
        # step1: lstrip s
        for i, l in enumerate(s.lstrip(' ')):
        
        # step2: check the sign of the first character
            if i == 0 and (l == '-' or l == '+'):
                if l == '-': sign = -1
                continue
        
        # step3: read until it reaches non-digit character
            try:
                int(l)
                int_str += l
                
            except:
                break
        
        if int_str == '':
            return 0
        
        else:
            ans = sign*int(int_str)
            if ans < -2**31: return -2**31
            if ans > 2**31-1: return 2**31-1
            return ans

• step1은 lstrip()으로 해결하였다.
• step2는 s의 첫번째 문자의 부호를 확인한다.
• step3에서 try문을 통해 문자에 int()를 적용하였을때 에러가 생기면 숫자가 아니라는 의미이므로 except()문을 실행하여 반복문을 빠져나가게 만든다.

결과

Runtime: 50 ms, faster than 64.53% of Python3 online submissions for String to Integer (atoi). Memory Usage: 13.8 MB, less than 98.80% of Python3 online submissions for String to Integer (atoi).

풀이 1

class Solution:
    def myAtoi(self, string):
        """
        :type str: str
        :rtype: int
        """
        match = re.match('^\s*[+|-]?\d+', string)
        
        if match:
            integer = int(match.group())
            return max(-(1 << 31), min(integer, (1 << 31) - 1))
        
        return 0

중요내용

• 정규표현식의 각 문자가 의미하는 바는 다음과 같다:
  1. \s는 whitespace를 의미한다.
  2. *는 앞의 문자가 무한대로 반복(0번도 포함)될 수 있다는 의미이다.
  3. []는 문자 클래스로, ‘[]안에 포함된 문자들과 매치’를 의미한다.
  4. ?는 앞의 문자가 있어도 되고 없어도 된다는 것을 의미한다.
  5. \d는 숫자와 매치됨을 의미한다.
  6. +는 앞의 문자가 최소 1번 이상 반복될 수 있다는 의미이다.
  7. match.group은 매치된 문자열을 리턴하는 메서드이다.
• max(-(1 « 31), min(integer, (1 « 31) - 1))는 특정 값의 범위 안에 포함되는지 여부를 확인하는 표현이므로 잘 기억해두자.

---

10. Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:

• ’.’ Matches any single character.
• ‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

입력: s = “aa”, p = “a*”

출력: True

내 풀이

풀지 못하였다.

풀이 1

class Solution(object):
    def isMatch(self, s, p):
        if not p: return not s
        # step 4
        if not s: return len(p) > 1 and p[1] == '*' and self.isMatch(s, p[2:])
        
        # step 1
        Matched = (p[0] == '.' or p[0] == s[0])
        
        if len(p) > 1 and p[1] == '*':
        # step 3                                           # step 5
            return (Matched and self.isMatch(s[1:], p)) or self.isMatch(s, p[2:])
            
                           # step 2
        return Matched and self.isMatch(s[1:], p[1:])

중요내용

• 위의 코드는 다음과 같은 순서로 이루어진다.
  1. Matched는 s와 p의 같은 인덱스에 위치한 문자가 일치하는지 여부를 검사한다.
  2. 마지막에 self.isMatch(s[1:], p[1:])는 ‘.’와 ‘*‘을 제외한 문자가 서로 일치하는지 검사한다
  3. (Matched and self.isMatch(s[1:], p))는 ‘*‘에 따라 문자가 알맞게 작성되었는지 검사한다.
  4. (return len(p) > 1 and p[1] == ‘*’ and self.isMatch(s, p[2:])) 는 3번에 의해 실행된 재귀구조에 대해 별칭에 따라 문자가 알맞게 작성되었는지 검사한다.
  5. isMatch(s, p[2:])는 * 다음에 나타나는 문자에 대해서 일치여부를 검사한다. 즉, 1~3번의 과정을 p가 끝날때까지 반복한다.
• 배열을 인덱싱할때 인덱스 값이 배열의 길이를 초과하면 에러가 생기나 슬라이싱은 None을 리턴한다.