One Pager Cheat Sheet
- Write a function
detectSubstring
to detect a substring within a given string, avoidingString
class's built-insubstring
orsubstr
method, withO(n)
time complexity andO(1)
space complexity, and handle strings of length ≤100000
. - We should
reason out
what we need to do before diving into the logic of solving a simple example like whether acar
is incarnival
. - We can use the
two-pointer technique
to compare two strings and check if one is a substring of the other by writing afor-loop
to compare the characters at each index and discoverhow far we can extend our match
when we find an initial one. - We can use an
idxOfStart
variable and aj
index to determine if a string contains a substring by checking character-by-character whether they match or not. - The code needs two slight adjustments to handle duplicate characters and accurately obtain the index of the start of matches, and its complexity is more accurately expressed as
O(n*m)
, wherem
is the length of the substring. - The number of comparisons made for the given code in the given test case is 12, which is
n * m
(6 * 3
). - With the two-pointer method, the time complexity for solving the given test case problem is
O(mn)
and a constantO(1)
space is used, although the Rabin-Karp algorithm may provide a more optimalO(n)
time complexity solution.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
56
}
var assert = require('assert');
​
function detectSubstring(str, subStr) {
let idxOfStart = 0,
j = 0;
​
for (i = 0; i < str.length; i++) {
// if match, compare next character of subStr with next of string
if (str[i] == subStr[j]) {
j++;
if (j == subStr.length) {
return i - (subStr.length - 1);
}
} else {
i -= j;
j = 0;
}
}
​
return -1;
}
​
// console.log(detectSubstring('ggraph', 'graph'));
// console.log(detectSubstring('geography', 'graph'));
// console.log(detectSubstring('digginn', 'inn'));
​
try {
assert.equal(detectSubstring('thepigflewwow', 'flew'), 6);
​
console.log(
'PASSED: ' + "`detectSubstring('thepigflewwow', 'flew')` should return `6`"
);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Alright, well done! Try another walk-through.
If you had any problems with this tutorial, check out the main forum thread here.