[Algorithm] Leetcode_ String to Integer (atoi)

JAsmine_log·2024년 5월 14일

String to Integer (atoi)

Problem

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

The algorithm for myAtoi(string s) is as follows:

Whitespace: Ignore any leading whitespace (" ").
Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present.
Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.
Return the integer as the final result.

Example 1:

Input: s = "42"
Output: 42
Explanation:

The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^

Example 2:

Input: s = " -042"
Output: -42
Explanation:

Step 1: " -042" (leading whitespace is read and ignored)
^
Step 2: " -042" ('-' is read, so the result should be negative)
^
Step 3: " -042" ("042" is read in, leading zeros ignored in the result)
^

Example 3:

Input: s = "1337c0d3"

Output: 1337

Explanation:

Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
^

Example 4:

Input: s = "0-1"

Output: 0

Explanation:

Step 1: "0-1" (no characters read because there is no leading whitespace)
^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
^

Example 5:

Input: s = "words and 987"
Output: 0
Explanation:
Reading stops at the first non-digit character 'w'.

Constraints:

0 <= s.length <= 200
s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Analysis and Solution

01 제공된 문자열(str) 탐색한다
02 먼저 나온 모든 whitespace 을 건너뛴다
ex: " -123456" --> "-123456"
03 signed 문자(+/-)를 확인한다
예: "-123456". +이면 변수(boolean) isNegative를 true로 설정하고,
-이면 isNegative를 false로 설정합니다.
04 남은 문자에서 문자형식의 숫자를 찾아('0'-'9')를 찾아 계속 결과를 반환한다
이 때, 숫자가 아닌 문자가 나타날 때까지 탐색한다.
예: "-123456" --> -123456
* 참고: 위의 01~03단계를 수행한 후, 탐색할 수 있는 문자는 영문(소문자 및 대문자), 숫자(0-9), ' ', '+', '-')이다.
* 문자가 먼저 나오면 0을 반환한다. 예: "abc-123456" --> 0
Integer 범위의 초과/미만이면 round한다

Code

//https://leetcode.com/explore/featured/card/top-interview-questions-easy/127/strings/884/
class Solution {
   public int myAtoi(String str) {
    
    final int len = str.length();
    
    if (len == 0) return 0;
    
    int index = 0;
    
    while (index < len && str.charAt(index) == ' ') ++index;
    
    boolean isNegative = false;
    
    if (index < len) {
      if (str.charAt(index) == '-') {
        isNegative = true;
        ++index;
      } else if (str.charAt(index) == '+'){
          ++index;
      }
    }
    
    int result = 0;
    
    while (index < len && isDigit(str.charAt(index))) {
     
      int digit = str.charAt(index) - '0';
      
      if (result > (Integer.MAX_VALUE / 10) || (result == (Integer.MAX_VALUE / 10) && digit > 7)){
          return isNegative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
      }
      
      result = (result * 10) + digit;
      
      ++index;
    }
      
    return isNegative ? -result : result;
  }
  
  private boolean isDigit(char ch) {
    return ch >= '0' && ch <= '9';
  }
}