I'm trying to find the substring in string using O(N) complexity. The following is the code I have written. It returns undefined and I don't know why. Please let me know what is going wrong in my code.
let omg = "omg";
let omgi = "omjiklmonomgib";
function stringSearch(smallString, bigString) {
let left = 0;
let right = left (smallString.length - 1);
while (left > right) {
if (smallString[left] === bigString[left]) {
if (smallString[right] === bigString[right]) {
left ;
right--;
if (left === right) {
if (smallString[right] === bigString[left]) {
return true;
} else if (right === left 1) {
if (smallString[right] === bigString[right] && smallString[left] === bigString[left]) {
return true;
} else {
left = right 1;
right = left (smallString.length - 1);
}
}
}
}
}
}
}
console.log(stringSearch(omg, omgi)); //Undefined
CodePudding user response:
I see a couple of issues. First, the code doesn't have a return statement for every logical branch. I mean that, for every condition in an if, then, else statement, the code should have a return statement or some sort of control-flow statement (e.g. a recursive call or a continue) that will eventually lead to a return statement.
The second issue is the while
loop. Supposedly, right
should be greater than left
from the beginning of the function (unless the length of smallString
is 0) because right
is the length of smallerString
minus 1. The while
condition is left > right
, so nothing inside of the while will be executed unless smallString
has a negative length (which it doesn't).
By the way, if you want to check the entire bigString
, you will need to iterate over bigString
, not smallString
. If you are only checking smallString.length
characters, you won't be checking the entire bigString
. Figuring out how to write this function is a good exercise, so I will leave the writing of it to you and refrain from providing an implementation myself. Keep up the good work!
CodePudding user response:
From what I understand, you're just remaking String.prototype.match. Try checking this out, as it would probably be an easier way to do what you're saying.
If you really wanna use this, I can give you some tips.
First of all, you should have a "cache" variable and another variable which will be found
(it'll be a boolean, so set it to false). The "cache" variable will store the text, and the other one will store whether you found the smallString
.
Basically, you loop through every character and store however long smallString
characters in the variable. Once the "cache" variable is the same length as smallString
, run an if statement on it. If it's not equal, remove the first character of the "cache". Next time iteration in the loop, it'll add another character. You then do the same as before, run an if statement and if it's not equal remove the first character and continue the loop until you find it, or the string ends, and if you found it, set the boolean to true.