Menu
I was trying to solve this problem: https://leetcode.com/problems/longest-substring-without-repeating-characters/
The following code passed all tests in 44 ms.
for (int i = 0; i < s.length(); i++){
if (!mp.containsKey(s.charAt(i))){
mp.put(s.charAt(i), i);
//max = Math.max(max, i-first+1);
}
else {
if (mp.get(s.charAt(i))+1>=first){
first = mp.get(s.charAt(i))+1;
}
mp.put(s.charAt(i), i);
//max = Math.max(max, i-first+1);
}
max = Math.max(max, i-first+1);
}
But the following code passed all tests in only 20 ms.
for (int i = 0; i < s.length(); i++){
if (!mp.containsKey(s.charAt(i))){
mp.put(s.charAt(i), i);
max = Math.max(max, i-first+1);
}
else {
if (mp.get(s.charAt(i))+1>=first){
first = mp.get(s.charAt(i))+1;
}
mp.put(s.charAt(i), i);
max = Math.max(max, i-first+1);
}
}
Why is there such a significant difference? The max value is changed only once in both of the samples but changing it in the if-else statements is far more efficient than changing it at the end of the for loop. Is this an exception or should we follow this standard whenever coding?
368
No, the for loop has more precedence over the if/else loop. That means that in the order of precedence for comes first. For Loops will execute a block of code a specified number of times. The if/else loop is a conditional statement (do this or else do that).
No there is no speed difference as every loop whether it be a for, do, or while loop becomes exactly the same. But instead of just accepting an answer let's research it.
An if statement lets your program know whether or not it should execute a block of code. Comparison-based branching is a core component of programming. The concept of an if-else or switch block exists in almost every programming language.
An if statement checks if an expression is true or false, and then runs the code inside the statement only if it is true. The code inside the loop is only run once... A while statement is a loop. Basically, it continues to execute the code in the while statement for however long the expression is true.
On simplifying (not early optimizing, see max!) one gets
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
Integer n = mp.get(ch):
if (n != null) {
first = Math.max(first, n + 1);
}
mp.put(ch, i);
max = Math.max(max, i - first + 1);
}
Remark the double put of value i in the original version. If the first Math.max is replaced with an if, the code might be faster.
It is hard to make a statement w.r.t. to speed here for the two original versions, maybe the hotspot compiler saw the redundancy. Or whatever.
It would be nice seeing a java 8 version, using mp.putIfAbsent or such, but that might meke it slower.
145
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
