Leetcode – Defanging an IP Address Solution

Spread the love

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.

Problem Description

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 “[.]”.

Example:

Input: address = "1.1.1.1"
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

Time Complexity:

The time complexity is O(n), where n is the length of the address string.

Space Complexity:

The space complexity is O(n) as well, due to the storage needed for the new string.

Using Python’s replace( ) Method

Python’s string 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('.', '[.]')

Time Complexity:

The time complexity for this approach is O(n), as the replace() method needs to traverse the entire string once.

Space Complexity:

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)

Time Complexity:

This method also has a time complexity of O(n).

Space Complexity:

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))

Time Complexity:

The time complexity for this approach is O(n).

Space Complexity:

The space complexity remains O(n).

Conclusion

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.

Leave a Reply