Comment on page

String

A string is actually an array of unicode characters.
String Comparison
String has its own compare function
Can we use "==" to compare two strings?
Depends on
Does the language support operator overloading?
Yes (like C++), we may use "==" to compare strings
No (like Java), we may not use "==" to compare two strings. "==" actually compares whether these two objects are the same object.
For Java, use
s1.equals(s2)
or
s1.compareTo(s2) == 0
Immutable or Mutable
In some languages (like C++), string is mutable, while in Java, string is immutable
Time Complexity of Built-in Operations
For instance, if the length of the string isN, the time complexity of both finding operation and substring operation isO(N).
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s1 = "Hello World";
​
        // 1. concatenate
        s1 += "!";
        System.out.println(s1);
​
        // 2. find
        System.out.println("The position of first 'o' is: " + s1.indexOf('o'));
        System.out.println("The position of last 'o' is: " + s1.lastIndexOf('o'));
​
        // 3. get substring
        System.out.println(s1.substring(6, 11));
    }
}
Beware of String Concatenation in Java
In Java, since the string is immutable, concatenation works by first allocating enough space for the new string, copy the contents from the old string and append to the new string.
In Java, using "+" for string concatenation, the time complexity will be O(n)
For the following, total time complexity in total will be O(n^2)
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}
Mutate String in Java
1. convert it to a char array
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "Hello World";
        char[] str = s.toCharArray();
        str[5] = ',';
        System.out.println(str);
    }
}
2. use some other data structures like StringBuilder
The below code runs in O(n) time complexity.
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        int n = 10000;
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            str.append("hello");
        }
        String s = str.toString();
    }
}

Shortest Word Distance II

Rotate String

Last modified 3yr ago