Usually I would expect a String.contains() method, but there doesn’t seem to be one.
What is a reasonable way to check for this?
질문에 대한 답변
ECMAScript 6
introduced String.prototype.includes:
const string = "foo"; const substring = "oo";
console.log(string.includes(substring)); // trueString.prototype.includes is case-sensitive and is not supported by Internet Explorer without a polyfill.
In ECMAScript 5 or older environments, use String.prototype.indexOf, which returns -1 when a substring cannot be found:
var string = "foo"; var substring = "oo";
console.log(string.indexOf(substring) !== -1); // trueChecking weather a string ‘str2’ containing substring ‘str1’ without using any pre-built method in JavaScript.
Since, multiple occurrences of substring in a string will also be considered as substring. So, it will definitely return true. But In addition, if substring occur more than once, we’re going to return number of occurrences.
Test Cases:
Input:- str2:’chandan’, str1:’ch’ Output:- true
Input:- str2:’chandan’, str1:’han’ Output:- true
Input:- str2:’chandan’, str1:’had’ Output:- false
Input:- str2:’chandan’, str1:’anh’ Output:- false
Input:- str2:’chandan’, str1:’an’ Output:- 2
Time & Space Complexity:-
T.C: O(N) & S.C: O(1) when, N is the length of string ‘str2’
function checkSubstring(str2, str1) {
let i=0,
j=0,
count=0;
while(j<str2.length){
if(str2[j]===str1[i]){
i++;
j++;
}else{
j++;
i=0;
}
if(i===str1.length){
count++;
i=0;
}
}
if(count===1) return true;
if(count===0) return false;
if(count>1) return count;
} checkSubstring('chandan', 'ch'); checkSubstring('chandan', 'han'); checkSubstring('chandan', 'had'); checkSubstring('chandan', 'anh'); checkSubstring('chandan', 'an'); Another alternative is KMP (Knuth–Morris–Pratt).
The KMP algorithm searches for a length-m substring in a length-n string in worst-case O(n+m) time, compared to a worst-case of O(n⋅m) for the naive algorithm, so using KMP may be reasonable if you care about worst-case time complexity.
Here’s a JavaScript implementation by Project Nayuki, taken from https://www.nayuki.io/res/knuth-morris-pratt-string-matching/kmp-string-matcher.js:
// Searches for the given pattern string in the given text string using the Knuth-Morris-Pratt string matching algorithm. // If the pattern is found, this returns the index of the start of the earliest match in 'text'. Otherwise -1 is returned. function kmpSearch(pattern, text) {
if (pattern.length == 0)
return 0; // Immediate match
// Compute longest suffix-prefix table
var lsp = [0]; // Base case
for (var i = 1; i < pattern.length; i++) {
var j = lsp[i - 1]; // Start by assuming we're extending the previous LSP
while (j > 0 && pattern[i] !== pattern[j])
j = lsp[j - 1];
if (pattern[i] === pattern[j])
j++;
lsp.push(j);
}
// Walk through text string
var j = 0; // Number of chars matched in pattern
for (var i = 0; i < text.length; i++) {
while (j > 0 && text[i] != pattern[j])
j = lsp[j - 1]; // Fall back in the pattern
if (text[i]
== pattern[j]) {
j++; // Next char matched, increment position
if (j == pattern.length)
return i - (j - 1);
}
}
return -1; // Not found }
console.log(kmpSearch('ays', 'haystack') != -1) // true console.log(kmpSearch('asdf', 'haystack') != -1) // false