Jobs

Interviews

Discussions

Defanging an IP Address

Easy

Robinhood

1 view

Topics:

Strings

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

The given address is a valid IPv4 address.

Try coding it in LeetCode

Defanging an IP Address

Easy

Robinhood

1 view

Topics:

Strings

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

The given address is a valid IPv4 address.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input IP address ever be null or empty?
Is the given IP address guaranteed to be a valid IPv4 address as per the stated format (x1.x2.x3.x4 where each xi is between 0 and 255)?
What should I return if the input IP address is invalid?
Should I modify the input string directly (in-place), or should I return a new string?
Are there any memory constraints that I should consider?

Brute Force Solution

Approach

The goal is to replace periods in an IP address with '[.]'. The brute force method essentially looks at each character in the IP address one by one. If it finds a period, it substitutes it.

Here's how the algorithm would work step-by-step:

Begin with the very first character of the IP address.
Check: Is this character a period?
If the character is a period, replace it with '[.]'.
If it's not a period, leave it alone.
Move to the next character in the IP address.
Repeat steps 2-5 until you have checked every character in the IP address.
You will now have the 'defanged' IP address where all periods are replaced.

Code Implementation

def defang_ip_address(ip_address):
    defanged_ip = ''
    for char in ip_address:
        # Need to check each character to see if it's a period
        if char == '.':

            defanged_ip += '[.]'

        # Otherwise, we add the character to the result as is
        else:

            defanged_ip += char

    return defanged_ip

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each character of the IP address once. Let n be the length of the IP address string. The algorithm inspects each of these n characters and performs a constant time comparison to check if it's a period. Since the number of operations grows linearly with the length of the IP address, the time complexity is O(n).

Space Complexity

O(N) – The described algorithm builds a new string by iterating through the input IP address. In the worst-case scenario, where every character is a character other than a period, a new string of length N, where N is the length of the original IP address, needs to be created to hold the defanged IP address. Therefore, the auxiliary space required is directly proportional to the length of the input IP address. This results in a space complexity of O(N).

Optimal Solution

Approach

The task is to replace each period in an IP address with '[.]'. Instead of trying to manipulate the string character by character, the best way is to think of it as replacing one chunk of text with another. We can achieve this with a simple and efficient technique.

Here's how the algorithm would work step-by-step:

Take the entire IP address as a single piece of text.
Find every occurrence of the period character ('.') within the IP address.
For each period found, replace it with the text '[.]'.
The resulting text will be the defanged IP address, with all periods replaced as required.

Code Implementation

def defang_ip_address(ip_address):
    # Replace all occurrences of '.' with '[.]'
    defanged_ip = ip_address.replace('.', '[.]')

    # Replacing allows creating the defanged IP easily

    return defanged_ip

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the IP address string of length n once to find and replace each occurrence of the period character. The replace operation itself takes constant time. Therefore, the time complexity is directly proportional to the length of the IP address, resulting in O(n) complexity.

Space Complexity

O(N) – The solution replaces each '.' with '[.]'. In the worst-case scenario, the IP address contains only '.' characters. Each replacement expands a single character to three characters. A new string with potentially more characters than the original IP address (of size N) will be created to store the defanged IP address. Therefore, the auxiliary space required is proportional to the size of the resulting string, which can be up to 3 times the number of periods in the input, but is bounded by the length of the new string. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null, or throw an IllegalArgumentException as appropriate for the language and API contract.
Input string contains no periods	Return the original string since no defanging is needed.
Input string contains only periods	Replace each period with '[.]' to produce '[.][.][.]...'.
Input string has leading or trailing periods	These periods should also be replaced with '[.]'.
Extremely long input string (performance)	Use a StringBuilder or similar mechanism to avoid string concatenation performance issues.
Invalid IPv4 address format (e.g., missing numbers, extra periods)	The problem statement specifies a 'valid IPv4 address', so this input could be considered out of scope, or an exception could be thrown.
Input string contains characters other than numbers and periods	If the problem statement limits the input to numbers and periods, other characters might be out of scope, or could throw an exception.
Very short IP address (e.g., '.'),	This still needs to be handled, which would result in '[.]' being returned.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input IP address ever be null or empty?
Is the given IP address guaranteed to be a valid IPv4 address as per the stated format (x1.x2.x3.x4 where each xi is between 0 and 255)?
What should I return if the input IP address is invalid?
Should I modify the input string directly (in-place), or should I return a new string?
Are there any memory constraints that I should consider?

Brute Force Solution

Approach

The goal is to replace periods in an IP address with '[.]'. The brute force method essentially looks at each character in the IP address one by one. If it finds a period, it substitutes it.

Here's how the algorithm would work step-by-step:

Begin with the very first character of the IP address.
Check: Is this character a period?
If the character is a period, replace it with '[.]'.
If it's not a period, leave it alone.
Move to the next character in the IP address.
Repeat steps 2-5 until you have checked every character in the IP address.
You will now have the 'defanged' IP address where all periods are replaced.

Code Implementation

def defang_ip_address(ip_address):
    defanged_ip = ''
    for char in ip_address:
        # Need to check each character to see if it's a period
        if char == '.':

            defanged_ip += '[.]'

        # Otherwise, we add the character to the result as is
        else:

            defanged_ip += char

    return defanged_ip

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the entire IP address as a single piece of text.
Find every occurrence of the period character ('.') within the IP address.
For each period found, replace it with the text '[.]'.
The resulting text will be the defanged IP address, with all periods replaced as required.

Code Implementation

def defang_ip_address(ip_address):
    # Replace all occurrences of '.' with '[.]'
    defanged_ip = ip_address.replace('.', '[.]')

    # Replacing allows creating the defanged IP easily

    return defanged_ip

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or null, or throw an IllegalArgumentException as appropriate for the language and API contract.
Input string contains no periods	Return the original string since no defanging is needed.
Input string contains only periods	Replace each period with '[.]' to produce '[.][.][.]...'.
Input string has leading or trailing periods	These periods should also be replaced with '[.]'.
Extremely long input string (performance)	Use a StringBuilder or similar mechanism to avoid string concatenation performance issues.
Invalid IPv4 address format (e.g., missing numbers, extra periods)	The problem statement specifies a 'valid IPv4 address', so this input could be considered out of scope, or an exception could be thrown.
Input string contains characters other than numbers and periods	If the problem statement limits the input to numbers and periods, other characters might be out of scope, or could throw an exception.
Very short IP address (e.g., '.'),	This still needs to be handled, which would result in '[.]' being returned.