The “Defanging an IP Address” problem is a straightforward string manipulation challenge that is commonly encountered in coding interviews, particularly for junior-level positions. This problem may appear to be trivial, but it serves as a useful exercise for understanding basic string manipulations in Python. In this exhaustive article, we will delve into the problem statement, examine multiple ways to solve the problem, and discuss the time and space complexities associated with each approach.
Here’s the problem statement as it appears on Leetcode:
Given a valid (IPv4) IP address, return a defanged version of that IP address. A defanged IP address replaces every period “.” with “[.]”.
Input: address = "184.108.40.206" Output: "1[.]1[.]1[.]1"
Naive Approach Using a Loop
The simplest way to tackle this problem is to initialize an empty string and traverse through each character of the input IP address. Whenever a period is encountered, append “[.]” to the result string; otherwise, append the character itself.
Here’s a Python implementation of this approach:
def defangIPaddr(address): defanged = '' for char in address: if char == '.': defanged += '[.]' else: defanged += char return defanged
The time complexity is O(n), where n is the length of the address string.
The space complexity is O(n) as well, due to the storage needed for the new string.
Using Python’s replace( ) Method
replace() method provides a much more straightforward way to solve this problem. It replaces all occurrences of a substring with another substring. Using this method, we can replace every “.” with “[.]” in one line.
def defangIPaddr(address): return address.replace('.', '[.]')
The time complexity for this approach is O(n), as the
replace() method needs to traverse the entire string once.
The space complexity is O(n) because a new string is created to store the defanged IP address.
Using Python’s join( ) Method and List Comprehension
An alternative approach is to use Python’s
join() method combined with list comprehension. In this approach, we iterate through the input string with list comprehension, replacing each period with “[.]” and then use
join() to concatenate the list into a single string.
def defangIPaddr(address): return ''.join('[.]' if char == '.' else char for char in address)
This method also has a time complexity of O(n).
The space complexity is O(n) for storing the list and the resulting string.
Using the map( ) Function
We can also use Python’s built-in
map() function to achieve this. The
map() function applies a given function to all items of an iterable (list, tuple, etc.). Here, we’ll use it to apply a lambda function that replaces each “.” with “[.]”, and then join them into a string.
def defangIPaddr(address): return ''.join(map(lambda x: '[.]' if x == '.' else x, address))
The time complexity for this approach is O(n).
The space complexity remains O(n).
The “Defanging an IP Address” problem is an excellent problem for beginners to grasp basic string manipulation in Python. While the problem can be quickly solved using Python’s built-in methods like
replace(), implementing a naive loop-based approach can be an instructive exercise for understanding how these built-in methods work behind the scenes.
The various approaches to solving this problem have similar time and space complexities of O(n). As such, the choice of method often comes down to readability and the specific requirements of a given situation.