This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

The IP address is invalid. Procedure

Given a valid IPv4 address address, return an invalid version of this IP address. Invalidating IP addresses means replacing each “.” with “[.]”.

Example 1:

Input: address = "1.1.1.1" Output: "1[.]1[.]1"Copy the code

Example 2:

Input: address = "255.100.50.0" output: "255 [.] 100 [.] 50 [.] 0"Copy the code

Thought analysis

Replace (“.”,”[.]”), which is to use the Java API to solve the problem in one step. This is not the answer that the interview is looking for. The first solution uses StringBuilder to judge and concatenate single characters one by one. The time complexity of this solution is O(n){O(n)}O(n), and the space complexity is also O(n){O(n)}O(n).

An alternative is to convert the string to an array of char[], invalidating it with an increase of 6 (2*3) in length, then iterating it into the new array, and finally converting it to a string. The time complexity of the solution is O(n){O(n)}O(n), and the space complexity is also O(n){O(n)}O(n).

The code shown

Solution 1: Iterate over the string, using StringBuilder splicing, time complexity is O(n){O(n)}O(n), space complexity is also O(n){O(n)}O(n).

public String defangIPaddr(String address) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < address.length(); i++) {
            if (address.charAt(i) == '. ') {
                sb.append("[the]");
            } else{ sb.append(address.charAt(i)); }}return sb.toString();
    }
Copy the code

Int (char[]); int (char[]); int (char[]); int (char[]); int (char[]); int (char[]); The time complexity of the solution is O(n){O(n)}O(n), and the space complexity is also O(n){O(n)}O(n).

    public String defangIpaddr(String address) {
        char[] a = address.toCharArray();
        int length = a.length + 2 * 3;
        char[] targetArray = new char[length];
        int j = 0;
        for (char c : a) {
            if ('. ' == c) {
                targetArray[j++] = '[';
                targetArray[j++] = '. ';
                targetArray[j++] = '] ';
            } else{ targetArray[j] = c; j++; }}return new String(targetArray);
    }
Copy the code

conclusion

When solving this kind of programming problems, we should pay special attention to remember to use API to solve the core logic of the algorithm simply and roughly. API is usually only used to solve part of the logic, rather than to replace the core logic. The time complexity and space complexity of the two solutions in this paper are O(n){O(n)}O(n).