8.字符串转换整数 (atoi)

自动机

时间复杂度：O(N)
空间复杂度：O(1)

func myAtoi(s string) int {
	// start signed number end
	const MinInt32, MaxInt32 = -1 << 31, 1<<31 - 1
	states := map[string][]string{
		"start":  {"start", "signed", "number", "end"},
		"signed": {"end", "end", "number", "end"},
		"number": {"end", "end", "number", "end"},
		"end":    {"end", "end", "end", "end"},
	}

	state := "start"
	ans := 0
	sign := 1

	for i := 0; i < len(s); i++ {
		index := get_state(s, i)
        curr := states[state][index]

		//fmt.Printf("state: %v\n", state)
		//fmt.Printf("curr: %v\n", curr)
		switch curr {
		case "end":
			//fmt.Printf("ans: %v\n", ans)
			//fmt.Printf("sign: %v\n", sign)
			return ans * sign
		case "number":
			ans = ans*10 + int(s[i]) - 48
			if ans * sign >= MaxInt32 {
				return MaxInt32
			}
			if ans * sign <= MinInt32 {
				return MinInt32
			}
		case "signed":
			if s[i] == '-' {
				sign = -1
			}
		}

        state = curr

	}

	return ans * sign
}

func get_state(s string, i int) int {
	switch {
	case s[i] == ' ':
		return 0
	case s[i] == '+' || s[i] == '-':
		return 1
	case s[i] >= '0' && s[i] <= '9':
		return 2
	}
	return 3
}