Comment on page
String
A string is actually an array ofunicode characters
.
String has its own
compare function
Can we use "==" to compare two strings?
Depends on
Does the language supportoperator 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
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 is
N
, 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));
}
}
In Java, since the string isimmutable
, 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";
}
}
}
// "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);
}
}
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();
}
}
Last modified 3yr ago