LeetCode 8. String conversion integer (ATOI)

8. String conversion integers (atoi)

Please come to realize a myAtoi(string s) function , Enable it to convert a string to a 32 Bit signed integer （ similar C/C++ Medium atoi function ）.

function myAtoi(string s) The algorithm is as follows ：

• Read in strings and discard useless leading spaces
• Check the next character （ Suppose you haven't reached the end of the character yet ） Positive or negative , Read the character （ If there is ）. Determine whether the final result is negative or positive . If neither exists , Suppose the result is positive .
• Read in the next character , Until you reach the next non numeric character or the end of the input . The rest of the string will be ignored .
• Convert the numbers read in the previous steps into integers （ namely ,“123” -> 123, “0032” -> 32）. If you don't read in the numbers , Then the integer is 0 . Change the symbol if necessary （ From step 2 Start ）.
• If the number of integers exceeds 32 Bit signed integer range [−231, 231 − 1] , You need to truncate this integer , Keep it in this range . say concretely , Less than −231 The integer of should be fixed to −231 , Greater than 231 − 1 The integer of should be fixed to 231 − 1 .
• Returns an integer as the final result .

Be careful ：

• The white space character in this question only includes the space character ' ' .
• Except for the leading space or the rest of the string after the number , Do not ignore Any other character .

Example 1：

 Input ：s = "42"
 Output ：42
 explain ： The bold string is the character that has been read in , The caret is the character currently read .
 The first  1  Step ："42"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："42"（ No characters are currently read in , Because it doesn't exist here  '-'  perhaps  '+'）
         ^
 The first  3  Step ："42"（ Read in  "42"）
           ^
 Parse to get an integer  42 .
 because  "42"  In scope  [-231, 231 - 1]  Inside , The final result is  42 .

Example 2：

 Input ：s = "   -42"
 Output ：-42
 explain ：
 The first  1  Step ："   -42"（ Read in leading space , But ignore ）
            ^
 The first  2  Step ："   -42"（ Read in  '-'  character , So the result should be negative ）
             ^
 The first  3  Step ："   -42"（ Read in  "42"）
               ^
 Parse to get an integer  -42 .
 because  "-42"  In scope  [-231, 231 - 1]  Inside , The final result is  -42 .

Example 3：

 Input ：s = "4193 with words"
 Output ：4193
 explain ：
 The first  1  Step ："4193 with words"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："4193 with words"（ No characters are currently read in , Because it doesn't exist here  '-'  perhaps  '+'）
         ^
 The first  3  Step ："4193 with words"（ Read in  "4193"; Because the next character is not a number , So read in stop ）
             ^
 Parse to get an integer  4193 .
 because  "4193"  In scope  [-231, 231 - 1]  Inside , The final result is  4193 .

Example 4：

 Input ：s = "words and 987"
 Output ：0
 explain ：
 The first  1  Step ："words and 987"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："words and 987"（ No characters are currently read in , Because it doesn't exist here  '-'  perhaps  '+'）
         ^
 The first  3  Step ："words and 987"（ Because of the current character  'w'  It's not a number , So read in stop ）
         ^
 Parse to get an integer  0 , Because I didn't read in any numbers .
 because  0  In scope  [-231, 231 - 1]  Inside , The final result is  0 .

Example 5：

 Input ：s = "-91283472332"
 Output ：-2147483648
 explain ：
 The first  1  Step ："-91283472332"（ No characters are currently read in , Because there are no leading spaces ）
         ^
 The first  2  Step ："-91283472332"（ Read in  '-'  character , So the result should be negative ）
          ^
 The first  3  Step ："-91283472332"（ Read in  "91283472332"）
                     ^
 Parse to get an integer  -91283472332 .
 because  -91283472332  Less than range  [-231, 231 - 1]  Lower bound of , The final result is truncated to  -231 = -2147483648 .

Tips ：

• 0 <= s.length <= 200
• s By the English letters （ Uppercase and lowercase ）、 Numbers （0-9）、' '、'+'、'-' and '.' form

Two 、 Method 1

automata

class Solution {
    
    public int myAtoi(String str) {
    
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
    
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}

class Automaton {
    
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map<String, String[]> table = new HashMap<String, String[]>() {
    {
    
        put("start", new String[]{
    "start", "signed", "in_number", "end"});
        put("signed", new String[]{
    "end", "end", "in_number", "end"});
        put("in_number", new String[]{
    "end", "end", "in_number", "end"});
        put("end", new String[]{
    "end", "end", "end", "end"});
    }};

    public void get(char c) {
    
        state = table.get(state)[get_col(c)];
        if ("in_number".equals(state)) {
    
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
    
            sign = c == '+' ? 1 : -1;
        }
    }

    private int get_col(char c) {
    
        if (c == ' ') {
    
            return 0;
        }
        if (c == '+' || c == '-') {
    
            return 1;
        }
        if (Character.isDigit(c)) {
    
            return 2;
        }
        return 3;
    }
}

Complexity analysis

• Time complexity ：O(n), among n Is the length of the string . We just need to process all the characters in turn , The time required to process each character is O(1).

• Spatial complexity ：O(1). The state of automata only needs constant space to store .