Hallo iedereen, Leo hier. Today’s topic is how to solve a Leetcode problem that asks to recreate the atoi function in Swift that C/C++ has.
This article is inspired by a Leetcode problem number 8 that is Integer to String(atoi) and we will solve that using Swift. We also have something interesting about integers in Swift and we will discuss it before start solving the Leetcode problem.
No more talking, let’s code! But first…
Painting of The Day
The painting today is called Number 14 a 1951 art piece by Jackson Pollock.
Deemed the “greatest painter alive” during his lifetime, Jackson Pollock was an American painter who was a major artist of abstract expressionist art in the 20th century. Pollock was expelled from two high schools during his formative years, the second one being Los Angeles Manual Arts School, where he was encouraged to pursue his interest in art.
In 1930, he moved to New York to study art and secured a job under the WPA Federal Art Project, a New Deal project, which allowed him to earn a living from his painting.
I chose this painting because we are parsing numbers here and the name of the painting is literally a number. If we parse the title of the painting in the atoi what number would result?
The Problem – Recreating C++ atoi Function in Swift
You have to recreate the atoi C/C++ function in Swift, which means, receiving a string and transforming it into a 32-bit integer.
Before diving into the problem something about how integers work in Swift is important to be stated. In the problem statement, it asks to the resulting integer always be 32-bit. This is a problem for Swift if you are thinking of using the `Int` object.
But why?
Generally speaking, you don’t need to select a specific size of integer to use. Swift provides an umbrella type, the Int, which has the same size as the current platform’s word size. That means every time you write in Swift Int you will never be very sure what size it would be because that type is platform-dependent.
For example:
- On a 32-bit platform, Int is the same size as Int32.
- On a 64-bit platform, Int is the same size as Int64.
We should follow the docs advice about using Integers:
Unless you need to work with a specific size of an integer, always use Int for integer values in your code. This helps code consistency and interoperability. Even on 32-bit platforms, Int can store any value between -2,147,483,648 and 2,147,483,647, and is large enough for many integer ranges.
That article is exactly the exception to the documentation advice. The problem statement says that the result should be an Int32 so we will need to put that boundary in our algorithm.
Solving the Leetcode problem
We will start solving the problem by saying that this is just one solution, you are more than welcome to suggest and make your own solution. I like when someone gives feedback about my code, the goal here is to build a learning environment.
That said let’s go to the algorithm, I’ll try to explain it with comments in it:
class Solution {
func myAtoi(_ s: String) -> Int {
var isNegative = false
var finalResult = 0
var startedToReadDigits = false
var nextShouldBeADigit = false
for stringfy in s.map { "\($0)" } { // transforming the input string into a string map
let possibleDigit = Int(stringfy) // try to transform into a Int
if let possibleDigit = possibleDigit { // here we are checking if is a digit or not. If not could it be a sign + or -, or anything invalid
startedToReadDigits = true // when we begin to read digits we should go until the the end.
nextShouldBeADigit = true // this indicates that the next reading value should be a digit.
finalResult = (finalResult * 10) + possibleDigit // this is a classic way to read numbers from strings from left to right inserting the numbers in the right order. Ex: If the string was "45", first time it would be ( 0 *10 ) + 4, and the second pass it would be (4 * 10) + 5 , resulting in 45.
var realFinalResult = finalResult
if isNegative { // I need to check if it is negative before checking the boundaries.
realFinalResult = realFinalResult * -1
}
if realFinalResult > Int32.max { // checking Int 32-bit upper boundary
return Int(Int32.max) // clamp to Int32 max
}
if realFinalResult < Int32.min { // checking Int 32-bit bottom boundary
return Int(Int32.min) // clamp to Int32 min
}
} else { // if we enter here that means we are not reading a 0-9 character, is not a digit.
if nextShouldBeADigit { // if this is not we should finish the algorithm
return fixFinalSign(isNegative, finalResult: finalResult)
}
if stringfy == "-" { // checking if is negative and setting isNegative if needed
isNegative = true
nextShouldBeADigit = true
continue
}
if stringfy == "+" && startedToReadDigits == false { // same for the plus sign but now we just set the next should be a Digit
nextShouldBeADigit = true
continue
}
if stringfy == " " { // if is a empty string and we already started to read digits, we must finish the algorithm
if startedToReadDigits {
return fixFinalSign(isNegative, finalResult: finalResult)
}
continue
}
return 0 // If no digits were read, then the integer is 0 and that was stated in the problem in Leetcode
}
}
return fixFinalSign(isNegative, finalResult: finalResult)
}
func fixFinalSign(_ isNegative: Bool, finalResult: Int) -> Int {
if isNegative {
return Int(finalResult * -1)
} else {
return Int(finalResult)
}
}
}And that’s it!
Time and Space Complexity – Big O
The time complexity is linear, which means O(N). To be completely accurate the Big O would be O(2N) because we traverse the string two times, because of the mapping to String in the first for. But we are doing that just for convenience, you can change that to just traverse the char and transform it into a String if you want or use the char instead of String. Your call.
And the space complexity is also linear because for any N input we are creating an array of N to traverse. Could be O(1) if you work with just characters, maybe that could be a challenge for you?
More Algorithms
If you are excited about this topic as I’m you can check solutions for other problems here.
I would recommend Finding the symmetric difference in Swift which is an interesting way to use dictionaries to solve algorithmic problems. And solving a special palindrome in Swift problem that we use the two-pointer technique to solve.
Summary – Recreating C++ atoi Function in Swift
Today we studied how we could implement the C/C++ function in Swift and solve the String to Integer(atoi) Leetcode problem in Swift. We solved in linear time and space, O(N), and the challenge that I left to you is to make it in O(1) space.
We learned that Swift Int the object is platform-dependent so we should not always imply that it will behave the same always. Maybe in the future, we could have an even bigger Integer in Swift, who knows?
That’s all my people, today we finished the Architecture and iOS Tooling article closing the series about the beginning of iOS development. I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.
Thanks for reading and… That’s all folks.
Credits:
