LeetCode is an implementation of string strStr() — JavaScript

The title

Title link: leetcode-cn.com/leetbook/re…

Answer key

The topic is string matching, the classical question of data structure, the general textbook will provide two algorithms, BF solution and KMP solution;

1. Violence (BF) solution

/ * * *@param {string} haystack
 * @param {string} needle
 * @return {number}* /
var strStr = function(haystack, needle) {

    
    const hLen = haystack.length,
        nLen = needle.length;

    if(nLen === 0) {
        return 0;
    }
    if(nLen <= hLen) {
        
        let i = j = 0;
        while(i < nLen && j < hLen) {
            
            if(haystack[j] === needle[i]) {
                i++;
                j++;
            }else {
                j = j - i + 1;
                i = 0; }}if(i === nLen) {
            returnj - i; }}return -1;
};
Copy the code

2. KMP solution

The principle of KMP is to make use of the characteristics of substring (the number of equal prefixes and suffixes is represented as the next array in the algorithm), so that the pointer to the main string does not need to backtrace. The key points of KMP are as follows:

• Understand the meaning of the next array of substrings and find the next array;
• How to use the next array transform for matching substrings;

/ * * *@param {string} haystack
 * @param {string} needle
 * @return {number}* /
var strStr = function(haystack, needle) {

    let hLen = haystack.length;
    let nLen = needle.length;
    if(nLen > hLen) {
        return -1;
    }
    if(nLen === 0) {
        return 0;
    }
    let next = new Array(nLen).fill(0); // Construct an array with fill
    

    // Find the next array
    for(let i = 1; i < nLen; i++) {for(let m = 1; m <= i; m++){let n = 0;
            let nex = 0;
            while((m + n)<=i && needle[n] === needle[m+n]) { // use m+n instead of m
                n++;
                nex++;
            }
            if((m + n) > i) {
                next[i] = nex;
                break; // Remember to break}}}// Matches the string
    let j = 0;
 
    for(let i = 0; i < hLen; i++) {// Here is less than hLen, because it is entirely possible to have a loop of hlen-nlen < I < hLen

        let flag = 0;
        while(j < nLen) {
            if(haystack[i] === needle[j]) {
                i++;
                j++;
                flag = 1;
            }else {
                break; }}if(nLen === j) {
            return i - j;
        }else if(0 === j) { // Next [j] = next[j] = 0;
            continue;
        }else {

            j = next[j-1]; // Change the subscript j of the substring using the next array instead of backtracking the subscript I of the main string

            i--; // Haystack [I] is the same as haystack[I]}}return -1;

};
Copy the code

3. Use the API provided by JS directly

This is a very fast, and will make the program space-time complexity is very low method;

Because those JS engines are big god come out, they are generally with the best algorithm to achieve JS API;

But this is not recommended for learning algorithms and practicing algorithms, because it does not improve our algorithm ability;

var strStr = function(haystack, needle) {

    return haystack.indexOf(needle);

};
Copy the code

If you have a better way of thinking and reconciliation, welcome to discuss ah ~

Juejin. Cn/post / 700669…