How below code have two different complexities?
I am solving one question of leetcode and while solving I have written one solution which is comparing if a part of string is palindrome or not. But when comparing with customized code of Time Complexity O(N*N) then it exceeds the given time limit (TLE).
But when I check equality of two strings after creating substrings of them then it does not give TLE even if the time complexity is O(N*N), N for outer loop and N for creating substring and comparing them.
Question:
214. Shortest Palindrome
You are given a string s. You can convert s to a palindrome by adding characters in front of it.
Return the shortest palindrome you can find by performing this
transformation.Example 1:
Input: s = “aacecaaa”
Output: “aaacecaaa”
Example 2:
Input: s = “abcd”
Output: “dcbabcd”
Solution that exceeds the time limit:
var shortestPalindrome = function(s) {
const n = s.length;
const rev = s.split("").toReversed().join("");
let f = (i) => {
for(let j = 0; j < n-i; j++) {
if(rev[i+j] != s[j]) {
return false;
}
}
return true;
}
for(let i = 0; i < n; i++) { \ this looping for n times
if(f(i)) { \ roughly taking n time for comparison
return rev.substr(0, i) + s;
}
}
return "";
};
Working solution:
var shortestPalindrome = function(s) {
const n = s.length;
const rev = s.split("").toReversed().join("");
for(let i = 0; i < n; i++) { \ this looping for n times
if(rev.substr(i) == s.substr(0, n-i)) { \ this line must be taking O(N) right?
return rev.substr(0, i) + s;
}
}
return "";
};
Please explain how these two solutions are different.
6