Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

Implement the strStr() function.

Given a Haystack string and a needle string, find the first place in the haystack string where the needle string appears (starting at 0). If it does not exist, return -1.

Example 1: Input: haystack = "hello", needle = "ll" Output: 2 Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1 Description: What value should we return when needle is an empty string? This is a good question to ask in an interviewCopy the code

 

Ii. Thinking analysis:

  • The simplest is indexOf to find;
  • And then I thought I could intercept strings
    • Substr (start [, length]) The index of the first character is 0. Start Mandatory LENGTH Optional
    • Substring (start [, end]) The index of the first character is 0. Start Mandatory end Optional

Three, AC code

/** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function(haystack, needle) { return haystack.indexOf(needle); }; Execution time: 68 ms Memory consumption: 37.9 MBCopy the code

Four,

  • Intercept string
/** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function(haystack, needle) { let L = needle.length; let n = haystack.length; for (let start = 0; start < n - L + 1; start++) { if (haystack.substr(start, L) == needle) { console.log(start) return start; } } return -1; }; /** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function(haystack, needle) { let L = needle.length; let n = haystack.length; for (let start = 0; start < n - L + 1; start++) { if (haystack.substring(start, start + L) == needle) { return start; } } return -1; }; Status: Elapsed time: 80 ms Memory consumption: 39 MBCopy the code
  • There are KMP algorithms in other languages

For reference only

Refer to the topic

  • Force button (LeetCode)